Potenze avide

[Leonida]

Trovare tutti i numeri primi $p$ tali che:
\[
p \cdot (2^{p-1} -1) = n^k
\]
con $n$ intero positivo e $k$ intero positivo $> 1$.

[wall98]

Funziona per $ p=3 $ e non funziona per i primi minori uguali a 5, dunque $ p \ge 5 $

Deve essere $ p(2^{p-1}-1)=p^k \cdot a^k \longrightarrow 2^{p-1}-1=p^{k-1} \cdot a^k $ con $ MCD(a,p)=1 $

Notiamo come però $ 2^{p-1}-1 $ contiene un solo fattore p, infatti p divide certamente quella differenza per fermat, ma $ p^2 $ no, visto che $ 2^{p^2-2} \equiv 1 \pmod{p^2} $ e $ MCD(p-1, p^2-2)=1 $, infatti $ MCD(p-1, p^2-2)=MCD(p-1, p^2-2-p+1)=MCD(p-1, p^2-2-p+1-p+1)=MCD(p-1, p^2-2p=p(p-2)) $ e visto che se un intero positivi diverso da 1 divide p-1 non puo dividere $ p(p-2) $, l'MCD tra $ p-1, p^2-2 $ divide 1, cioè sono coprimi e l' ordine moltiplicativo non divide entrambi, di conseguenza non puo essere $ 2^{p-1} \equiv 1 \pmod{p^2} $ perchè sarebbe congruo anche a $ 2^{p^2-2} $ e abbiamo appena dimostrato che non è cosi.

Quindi $ k=2 $, quindi abbiamo da risolvere $ 2^{p-1}-1=a^2 \cdot p \longrightarrow 2^{p-1}-p \cdot a^2=1 $, che sembra essere una pell, che però conosco solo di nome (quindi magari è risolubile anche da qua, nell'incertezza vado avanti..).

Fattorizziamo come $ a^2=\frac{(2^{(p-1)/2}-1)(2^{(p-1)/2}+1)}{p} $, p chiaramente puo essere contenuto in uno solo dei due fattori, che sono coprimi tra loro visto che l'MCD divide la loro differenza, che è 2, e sono entrambi dispari, l'altro fattore sara un quadrato, ma un quadrato mod 4 è congruo a 1, essendo $ p \ge 5 $ si ha che l'unico fattore che puo esserlo è $ (2^{(p-1)/2}+1) $

Dunque $ 2^{(p-1)/2}+1=m^2 \longrightarrow (m-1)(m+1)=2^{(p-1)/2} $, quindi sia $ m-1 $ che $ m+1 $ devono essere potenze di 2, accade solo con $ m=3 $, che procedendo a ritroso si trova $ p=7 $, che funziona.

Nota: non ci è venuta la soluzione con p=3 perchè in $ a^2=\frac{(2^{(p-1)/2}-1)(2^{(p-1)/2}+1)}{p} $il numero $ 2^{(p-1)/2}-1 $ sarebbe stato l'unico caso in cui $ 4 \not \mid 2^{(p-1)/2} $.

EDIT: l'ho modificata che c'era un errore

[karlosson_sul_tetto]

[...]visto che $ 2^{p^2-2} \equiv 1 \pmod{p^2} $

Non capisco come ottieni ciò... usando $a^{\phi(n)}\equiv 1 \pmod{n}$? Perché secondo questa formula $\phi(p^2)=p(p-1)$ (bisogna togliere $p,2p,3p,4p \ldots(p-1)p, p^2$).
RIEDIT: l'EDIT era una cazzata.

[Drago96]

visto che $ 2^{p^2-2} \equiv 1 \pmod{p^2} $

Ciò mi pare ben falso... è vero con esponente pari a $ p^2-p $ invece
Tuttavia è probabilmente vero il fatto che quel fattore non sia divisibile per $ p^2 $...

[wall98]

[...]visto che $ 2^{p^2-2} \equiv 1 \pmod{p^2} $

Non capisco come ottieni ciò... usando $a^{\phi(n)}\equiv 1 \pmod{n}$? Perché secondo questa formula $\phi(p^2)=p(p-1)$ (bisogna togliere $p,2p,3p,4p \ldots(p-1)p, p^2$).

Gia quindi in sostanza rimane da dimostrare (se è vero) che quel fattore non è divisibile per $ p^2 $

[wall98]

Karlosson credo che quella sia la phi, non l'ordine moltiplicativo, ma credo che visto che $ p^2 $ è coprimo con 2 "teoricamente" devono essere generate tutte le classi di resto modulo p (coprime con p) in esattamente $ p(p-1) $ elevazioni a potenza, e non prima, quindi posso supporre che quello sia l'ordine moltiplicativo (?) e che, come hai detto tu, è il minimo intero positivo per il quale la potenza diventa 1

[karlosson_sul_tetto]

Si infatti ho sparato una grossa idiozia...era meglio se me ne stavo zitto e non editavo

[mate!!!]

Per la cronaca, questo è il problema 6 della prova di matematica del concorso di ammissione alla Scuola Superiore di Catania (http://www.scuolasuperiorecatania.it/ammissione/bando/) di quest'anno. Posto una possibile soluzione che dovrebbe funzionare.

Dobbiamo trovare tutti i primi \(p\) tali che \(p(2^{p-1}-1)=q^k\) con \(p\) primo e \(q\) e \(k\) interi positivi \((k>1)\).

Possiamo riscrivere l'espressione come \(p(2^{p-1}-1)=p^kn^k \Rightarrow (2^{p-1}-1)=p^{k-1}n^k\).

Sia \(p=2 \rightarrow (2^{2-1}-1)=2^{k-1}n^{k}=1\) ma \(k>1 \rightarrow\) assurdo!

Quindi \(p>2\): \(p\) è un primo dispari e dunque \((p-1)\)è pari e possiamo scomporre \((2^{p-1}-1)\) come una differenza di quadrati:

\((2^{\frac {p-1}{2}}-1)(2^{\frac {p-1}{2}}+1)=p^{k-1}n^{k}\)

I due fattori dell' LHS sono due numeri dispari consecutivi quindi sono coprimi e considerando il fatto che \((2^{\frac {p-1}{2}}-1)<(2^{\frac {p-1}{2}}+1)\) ci sono tre possibili casi:

\([1]\): \((2^{\frac {p-1}{2}}-1)=1\) and \((2^{\frac {p-1}{2}}+1)=p^{k-1}n^{k}\).

Dalla prima equazione otteniamo \(p=3\) che è la prima soluzione. Da ora in poi \(p>3\)

Sia \(n^k=x^ky^k\) con \(MCD(x,y)=1\)

\([2]\): \((2^{\frac {p-1}{2}}-1)=x^k\) e \((2^{\frac {p-1}{2}}+1)=y^kp^{k-1}\)

\([2a]\): \(k\) è pari: \(x^k\) è un quadrato perfetto e quindi è \(\equiv 1 \pmod{4}\), ma \((2^{\frac {p-1}{2}}-1) \equiv 3 \pmod{4}\) per \(p>3 \rightarrow\) assurdo!

\([2b]\): \(k\) è dispari: \((x^k+1)=(x+1)(x^{k-1}-x^{k-2}+...-x+1)=2^{\frac {p-1}{2}}\). Siccome \(p>3\) abbiamo che \(2^{\frac {p-1}{2}}>2\) dunque l' RHS è pari e non ha fattori dispari nella sua fattorizzazione. Quindi i fattori dell'LHS devono essere entrambi pari. Dunque \((x+1) \equiv 0 \pmod{2}\): l'espressione \((x^{k-1}-x^{k-2}+...-x+1)\) ha un numero dispari di addendi dispari \(\rightarrow\) assurdo!

\([3]\): \((2^{\frac {p-1}{2}}-1)=y^kp^{k-1}\) e \((2^{\frac {p-1}{2}}+1)=x^k\)

\([3a]\): \(k\) è pari: dalla seconda equazione \((x^{k/2}-1)(x^{k/2}+1)=2^{\frac {p-1}{2}} \rightarrow (x^{k/2}-1)\) e \((x^{k/2}+1)\) devono essere potenze di due con differenza due e l'unico possibile caso è \(2\) e \(4\) che si ottiene da \(x=3\) e \(k=2\). Quindi \(2^{\frac {p-1}{2}}=8 \rightarrow p=7\) che è la seconda soluzione.

\([3b]\): \(k\) è dispari: \((x^k-1)=(x-1)(x^{k-1}+x^{k-2}+...+x+1)=2^{\frac {p-1}{2}}\). Quindi (come in 2b) deve essere \((x-1) \equiv 0 \pmod{2}\) e l'espressione \((x^{k-1}+x^{k-2}+...+x+1)\) ha un numero dispari di addendi dispari ed è dunque dispari \(\rightarrow\) assurdo!

Questo prova che le uniche soluzioni sono \(p=3\) e \(p=7\).