131. $a^n\pm b^n=p^z$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

131. $a^n\pm b^n=p^z$

Messaggio da kalu » 12 ott 2012, 22:25

Qualcosa di generale e (credo) utile da risolvere e tenere bene a mente:

a) "Own". Trovare tutte le quintuple $ (a, b, n, p, z) $ di interi positivi, con gcd$ (a, b)=1 $, max$ \{a, b\}>1 $, $ n>1 $ dispari e $ p $ primo, tali che: $$a^n+b^n=p^z$$

b) "Own". Siano $ a, b, n, p, z $ interi positivi con gcd$ (a, b)=1 $, $ n>1 $, $ p $ primo, tali che: $$a^n-b^n=p^z$$ Dimostrare che $ n $ è primo.
Testo nascosto:
In un po' di thread abbastanza recenti potreste trovare più di un hint :!:
Forse basterà risolverne uno per avere il testimone :|
NB Gli "own" sono fra virgolette perchè si tratta di equazioni talmente generali che non si può credere che nessuno ci abbia pensato prima di me xD
Pota gnari!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 131. $a^n\pm b^n=p^z$

Messaggio da jordan » 13 ott 2012, 02:24

Difatti c'è qualcosa di molto piu' generale, noto come Teorema di Zsigsmondy, dimostrabile in via elementari (per il problema sopra,a prima vista e' sufficiente LTE):

Se $ \{a_n\}_{n=1}^\infty $ è una successione di numeri interi e $ p \in \mathbb{N} $ è un primo, si dice che $ p $ è un fattore primo primitivo (click) del termine $ a_n $, per qualche $ n=1, 2, \ldots $, se $ p $ divide $ a_n $ e $ n = \min\{k \in \mathbb{N}^+: p \mid a_k\} $. Allora

$\bullet$ 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 $.

$\bullet$ 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 $.
The only goal of science is the honor of the human spirit.

Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 131. $a^n\pm b^n=p^z$

Messaggio da kalu » 14 ott 2012, 09:51

Davvero interessante! Proverò a leggerne la dimostrazione. Beh chi vuol risolvere l'esercizio senza Zsigsmondy? E' vero, c'è poco in più di un buon uso di LTE...
Pota gnari!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Part 1

Messaggio da jordan » 14 ott 2012, 14:51

kalu ha scritto:Trovare tutte le quintuple $ (a, b, n, p, z) $ di interi positivi, con gcd$ (a, b)=1 $, max$ \{a, b\}>1 $, $ n>1 $ dispari e $ p $ primo, tali che: $$a^n+b^n=p^z$$
$\bullet$ Se $p=2$ siano $\alpha, \beta, A, B$ univocamente determinati tali che $a=2^A\alpha, b=2^B\beta$ e wlog $A\le B$ con $2\nmid \alpha\beta$; abbiamo
\[ 2^z=a^n+b^n=2^{nA}\left(\alpha^n+2^{n(B-A)}\beta^n\right) \]
Se $A\neq B$ allora $\alpha^n+2^{n(B-A)}\beta^n$ e' dispari, maggiore di $1$, e divide $2^z$, assurdo. Resta il caso $A=B$, allora $2^{z-nA}=\alpha^n+\beta^n$ e $z-nA=\upsilon_2(\alpha^n+\beta^n)=\upsilon_2(\alpha+\beta) \le \text{log}_2(\alpha+\beta)$. Per cui:
\[ \alpha^3+\beta^3\le \alpha^n+\beta^n=2^{z-nA}\le 2^{\text{log}_2(\alpha^2-\beta^2)-1} \le \alpha+\beta \implies \alpha=\beta=1 \]
Per cui esistono solo le soluzioni banali $(a,b,n,z)=(2^k,2^k,n,kn+1)$.

$\bullet$ Se $p\ge 3$, dato che $3\le a+b \mid a^n+b^n = p^z$, allora $a+b, a^n+b^n$ sono potenze di $p$. Per LTE:
\[ z=\upsilon_p(p^z)=\upsilon_p(a^n+b^n)=\upsilon_p(a+b)+\upsilon_p(n) \implies a^n+b^n=p^z \le p^{\text{log}_p(a+b)+\text{log}_p(n)}=n(a+b) \]
Per le medie $n(a+b)\ge a^n+b^n > \frac{1}{2^{n-1}}(a+b)^n \implies a+b < 2n^{\frac{1}{n-1}}\le 2\sqrt{3} \implies a+b \le 3$ cioè wlog $a=1, b=2$. Dobbiamo quindi risolvere
\[ 2^n+1=p^z \]
per qualche $n$ dispari $>1$, ma $3\mid 2^n+1^n \implies p=3$. Modulo $4$ abbiamo $z$ pari, per cui $2^n=(3^{\frac{z}{2}}+1)(3^{\frac{z}{2}}-1)$,entrambi i fattori sono potenze di $2$ e differiscono di $2$, per cui devono essere $2$ e $4$ da cui $z=2$. Da cui l'unica soluzione $2^3+1^3=3^2$. []
The only goal of science is the honor of the human spirit.

Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 131. $a^n\pm b^n=p^z$

Messaggio da kalu » 14 ott 2012, 15:30

Ok la parte a :) (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 $).
Facciamo che se entro alcuni giorni (pochi, diciamo solo 3) nessuno avrà risolto la parte b prenderai tu il testimone, altrimenti andrà avanti chi avrà risolto la b.
So che è abbastanza simile, ma c'è comunque dietro qualche idea in più..
Pota gnari!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Part 2.

Messaggio da jordan » 14 ott 2012, 15:50

kalu ha scritto:Ok la parte a (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 $).
Piu' che dimenticato, la soluzione risolve un problema piu' generale.
kalu ha scritto: Siano $ a, b, n, p, z $ interi positivi con gcd$ (a, b)=1 $, $ n>1 $, $ p $ primo, tali che: $a^n-b^n=p^z$. Dimostrare che $ n $ è primo.
Anche qui, eliminiamo l'ipotesi $\text{gcd}(a,b)=1$.

$\bullet$ Se $p=2$ allora $a^q-b^q\mid a^n-b^n=2^z$ cioè $a^q-b^q=2^{k_q}$ per qualche $k_q\in \mathbb{N}$, e ogni $q$ divisore di $n$. Se $n$ non è primo, esisteranno degli interi $\alpha, \beta$ maggiori di $1$ tali che $\alpha \mid n$ e $\alpha\beta \mid n$ e in particolare $a-b, a^{\alpha}-b^{\alpha},a^{\alpha\beta}-b^{\alpha\beta}$ sono tutte potenze di $2$. Possiamo assumere wlog che $a,b$ non siano entrambi pari. Se $a-b=1$ allora $a^n-b^n$ sarebbe dispari, per cui possiamo assumere wlog $a,b$ entrambi dispari, con $a>b$. Ora,se $q$ e' dispari allora $\upsilon_2(a^q-b^q)=\upsilon_2((a-b)(\sum_{i=0}^{q-1}{a^ib^{q-1-i}}))=\upsilon_2(a-b)$, ma $a^q-b^q>a-b$ e sono entrambe potenze di $2$. Questo significa che ogni divisore di $n$ e' pari, i.e. $n=2^k$ per qualche $k \in \mathbb{N}_0$. Ma allora $z=\upsilon_2(a^n-b^n)=\upsilon_2(a^2-b^2)+k-1 \le \text{log}_2(a^2-b^2)+k-1$. Allora $a^n-b^n=2^z\le \frac{n}{2}(a^2-b^2)$, cioè $f(a)\le f(b)$ dove $f(x):=x^n-\frac{n}{2}x^2$. Adesso $f'(x)=nx(x^{n-2}-1)$. Ricordiamo che $n$ e' una potenza di $2$: se fosse $2^2 \mid n$ allora $n \ge 4$ e $f'(x)$ sarebbe strettamente positiva per $x> 1$, che e'assurdo. Quindi $n$ deve valere $2$, che e' primo.

$\bullet$ Se $p\ge 3$ allora,come prima, se $n$ non e' primo, esisteranno degli interi $\alpha, \beta$ maggiori di $1$ tali che $\alpha \mid n$ e $\alpha\beta \mid n$ e in particolare $a-b, a^{\alpha}-b^{\alpha},a^{\alpha\beta}-b^{\alpha\beta}$ sono tutte potenze di $p$. Adesso $\upsilon_p(a^q-b^q)=\upsilon_p(a-b)+\upsilon_p(q)$ per cui ogni divisore di $n$ e' multiplo di $p$, i.e. $n=p^k$ per qualche $k\in \mathbb{N}_0$. Da cui $z=\upsilon_p(a^n-b^n)=\upsilon_p(a-b)+k=\text{log}_p(a-b)+k$, cioè $a^n-b^n=p^z=n(a-b)$, che puo' essere riscritto come $g(a)=g(b)$ con $g(x):=x^n-nx$. Ora $g'(x)=n(x^{n-1}-1)$, che e' strettamente positiva in $x>1$, dato che per ipotesi $n>1$. Per cui $g(x)$ e' strettamente crescente in $x>1$, assurdo. []
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Teorema di Zsigsmondy

Messaggio da jordan » 14 ott 2012, 15:53

Allego sotto anche la dimostrazione del teorema citato sopra:
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.
The only goal of science is the honor of the human spirit.

Avatar utente
kalu
Messaggi: 295
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 131. $a^n\pm b^n=p^z$

Messaggio da kalu » 14 ott 2012, 16:44

Vai pure col prossimo, e grazie per la dimostrazione del teorema :)
Pota gnari!

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 131. $a^n\pm b^n=p^z$

Messaggio da jordan » 14 ott 2012, 17:48

La tua soluzione passa per qualcosa di piu' intelligente/veloce che passare per la derivata?

Edit: in effetti bastava mostrare che $f(x+1)>f(x)$.. :wink:
The only goal of science is the honor of the human spirit.

Rispondi