fry ha scritto:Nel seguito supponiamo $ a,b $ interi tali che $ 1 \leq b < a $ e $ \gcd(a,b) = 1 $.
Preliminari. Vedi
qui.
Lemma 1. Se $ d,n \in \mathbb{N}^+ $, $ p \in \mathbb{P} $ soddisfano $ d < n $, $ d \mid n $ e $ p \mid \gcd(\Psi_d(a,b),\Psi_n(a,b)) $ allora $ p \mid n $.
Prova. Abbiamo $ p \mid \Psi_d(a,b) \mid a^d - b^d $ (vedi Teorema 1
qui) e essendo $ p \nmid ab $ sarà $ (ab^{-1})^d \equiv 1 \mod p $, ora se $ k := n /\ \! \! d $ allora
$ p \mid \Psi_n(a,b) \mid \displaystyle\frac{a^n - b^n}{a^d - b^d} = \sum_{j=0}^{k-1} a^{d(k-j-1)}b^{dj} \equiv a^{d(k-1)} k \bmod p $
quindi $ p \mid k \mid n $.
Lemma 2. Siano $ m,n \in \mathbb{N}^+ $,$ p \in \mathbb{P} $ con $ m > n $, se $ p \mid \gcd(\Psi_m(a,b),\Psi_n(a,b)) $ allora $ m /\ \!\! n = p^k $ per qualche $ k \in \mathbb{N}^+ $.
Prova. Facilmente $ p \nmid a,b $, definiamo $ \alpha := v_p(m) $ (vedi
qui) e $ m' := m /\ \!\! p^\alpha $ allora (vedi Corollario 2
qui)
$ 0 \equiv \Psi_m(a,b) \equiv \displaystyle \frac{\Psi_{m'}\big(a^{p^\alpha}, b^{p^\alpha}\big)}{\Psi_{m'}\big(a^{p^{\alpha-1}}, b^{p^{\alpha-1}}\big)} \bmod p $
dal
piccolo teorema di Fermat segue $ x^{p^\alpha} \equiv x \bmod p $ per ogni $ x \in \mathbb{Z} $ dunque $ 0 \equiv \Psi_{m'}\big(a^{p^\alpha}, b^{p^\alpha}\big) \equiv \Psi_{m'}\big(a, b\big) \bmod p $ e in maniera dal tutto analoga si trova $ p \mid \Psi_{n'}\big(a, b\big) $ dove $ n' := n /\ \! \! p^{v_p(n)} $.
Supponiamo $ m' > n' $, sia $ s := \gcd(m',n') < m' $ e abbiamo $ p \mid \gcd(a^{m'} - b^{m'}, a^{n'} - b^{n'}) = a^s - b^s $ quindi
$ p \mid a^s - b^s =\displaystyle \prod_{d \mid s} \Psi_d(a,b) $
e per il
lemma di Euclide esisterà un intero $ d \mid s $ tale che $ p \mid \Psi_d(a,b) $, del resto $ d \leq s < m' $ e dal Lemma 1 segue $ p \mid m' $, assurdo!
Allo stesso modo non può essere $ m' < n' $ quindi $ m' = n' $ da cui la tesi.
Lemma 3. Se $ n \in \mathbb{N}^+ $, $ p \in \mathbb{P} $ sono tali che $ p \mid n $ allora definiti $ \alpha := v_p(n) $, $ c := a^{p^{\alpha-1}} $ e $ d := b^{p^{\alpha-1}} $ abbiamo $ \Psi_n(a,b) > c^{p-2} $.
Prova. Se $ r := n /\ \! \! p^\alpha $ abbiamo
$ \displaystyle \Psi_n(a,b) = \frac{\Psi_r(c^p,d^p)}{\Psi_r(c,d)} = $$ \displaystyle\prod_{k \in {(\mathbb{Z}/n\mathbb{Z})}^*} \frac{c^p - \zeta_n^k d^p}{c - \zeta_n^k d} > \left(\frac{c^p - d^p}{c + d}\right)^{\varphi(r)} $
dove $ \zeta_n := e^\frac{2\pi i}{n} $ e $ \varphi(\cdot) $ è la
funzione di Eulero. Del resto $ c^p - d^p \geq c^{p-2}(c^2 - d^2) $ da cui la tesi.
Lemma 4. Ogni termine della successione $ \{\Psi_n(a,b)\}_{n=1}^\infty $ possiede almeno un fattore primo primitivo, con la sola eccezione dei casi in cui
i) $ n=2 $ e $ a+b $ è una potenza di 2, oppure
ii) $ a=2 $, $ b=1 $ e $ n=6 $.
Prova. Banalmente $ \Psi_1(a,b) $ ha sicuramente un fattore primo primitivo.
Supponiamo $ 2 \leq n \in \mathbb{N}^+ $ tale che $ \Psi_n(a,b) $ non abbia fattori primitivi, dal Lemma 1 e dal Lemma 2 segue che se $ p \in \mathbb{P} $ è tale che $ p \mid \Psi_n(a,b) $ allora $ p \mid n $.
Se $ n=2 $ allora $ \Psi_2(a,b) = a + b = 2^k $ per qualche $ k \in \mathbb{N}^+ $ (vedi Teorema 3
qui) i.e. la
i).
Se $ n > 2 $ allora $ \Psi_n(a,b) = p := \mbox{gpf}(n) $ (vedi Teorema 3
qui).
Se $ p=2 $ allora $ n=2^k $ con $ k \in \mathbb{N}^+ $, quindi (vedi Corollario 2
qui)
$ \Psi_n(a,b) = \Psi_2\big(a^{2^{k-1}},b^{2^{k-1}}\big) = $$ a^{2^{k-1}} - b^{2^{k-1}} \geq (b+1)^{2^{k-1}} - b^{2^{k-1}} > 2 $
assurdo, quindi $ p \geq 3 $.
Ora per il Lemma 3 con le stesse notazioni sarà $ c^{p-2} < p $ da cui $ p=3 $, $ c = 2 $ e $ d = 1 $ i.e. $ a=2 $ e $ b=1 $, quindi $ \alpha=1 $ e $ n \mid q(q-1) = 6 $ (vedi Teorema 3
qui) del resto poichè $ 3 \mid 2^n - 1 $ avremo $ 2 \mid n $ e in definitiva $ n=6 $ cioè la
ii).
Teorema 1 (di Zsigmondy, 1882). Dati $ a,b\in\mathbb{N} $, con $ 1 \le b < a $, ogni termine della successione $ \{a^n-b^n\}_{n=1}^\infty $ possiede almeno un fattore primo primitivo, con la sola eccezione dei casi in cui
i) $ n=2 $ e $ a+b $ è una potenza di 2, oppure
ii) $ a=2 $, $ b=1 $ e $ n=6 $.
Prova. Sia $ d := \gcd(a,b) $, se $ (a /\ \! \! d)^n - (b /\ \! \! d)^n $ ha un fattore primo primitivo allora anche $ a^n - b^n = d^n \big((a /\ \! \! d)^n - (b /\ \! \! d)^n\big) $ ce l'ha, quindi wlog possiamo supporre $ \gcd(a,b)=1 $ così che valgano i lemmi precedenti.
Se vale la
i) allora $ 2 \mid a - b $ e $ a^2 - b^2 = (a - b)(a + b) $ non ha fattori primitivi, se invece vale la
ii) allora $ a^n - b^n = 63 $ non ha fattori primitivi.
La tesi segue dal Lemma 4 una volta osservato che $ \Psi_n(a,b) \mid a^n - b^n $ per ogni $ n \in \mathbb{N}^+ $
Teorema 2 (di Zsigmondy, 1882). Dati $ a,b\in\mathbb{N} $, con $ 1 \le b < a $, ogni termine della successione $ \{a^n+b^n\}_{n=1}^\infty $ possiede almeno un fattore primo primitivo, con la sola eccezione del caso in cui $ a=2 $, $ b=1 $ e $ n=3 $.
Prova. Come prima wlog possiamo supporre $ \gcd(a,b)=1 $. Banalmente $ a + b $ ha un fattore primo primitivo e per ogni $ n \in \mathbb{N}^+ \setminus \{1\} $ abbiamo che $ \displaystyle a^n + b^n = \frac{a^{2n} - b^{2n}}{a^n - b^n} $ ha un fattore primo primitivo se $ a^{2n} - b^{2n} $ ha un fattore primo primitivo i.e. (dal Teorema 1) se $ n \neq 3 $.
Infine se $ a=2 $, $ b=1 $ e $ n=3 $ allora $ 2^3 + 1^3 = 9 $ non ha fattori primi primitivi.
(in realtà non ci sono affatto soluzioni banali perchè nel caso $ p=2 $ ti sei dimenticato delle ipotesi gcd$ (a, b)=1 $, max$ \{a, b\}>1 $).