Potenze di $5$ e $\varphi$

[Drago96]

Siano $m,n$ due interi positivi. Dimostrare che $$\displaystyle \varphi\left(5^m-1\right)=5^n-1 \implies \gcd(m,n)>1$$

[Lasker]

Suppongo per assurdo $\gcd(m,n)=1$, voglio mostrare che allora:
$$\varphi(5^m-1)\ne 5^n-1$$
Fatto:per ogni $m\geq 1$, si ha che $m\mid \varphi(5^m-1)$
Infatti osservo che $ord_{5^m-1}(5)=m$ perché deve essere $5^x-5^m+1\equiv 1 \pmod {5^m-1}$, e visto che $\gcd(5^m-1,5)=1$, posso dire che per il teorema di Eulero $ord_{5^m-1}(5)\mid \varphi(5^m-1)\Rightarrow m\mid \varphi(5^m-1)$.

Dunque per il lemma LHS è congruo a $0$ modulo $m$, mentre RHS, visto che $\gcd(m,n)=1$ e $ord_{5^m-1}(5)=m$ non può esserlo, assurdo.
Dunque la tesi è dimostrata (modulo enormi sviste ).
Edit: in effetti (come mi ha fatto notare Jordan) lo svarione c'è; vedrò di aggiustare/trovare la vera dimostrazione

[jordan]

Non capisco come concludi: prendi $m=3$ e $n=2$, si ha $\text{gcd}(m,n)=1$, $m\mid \varphi(5^m-1)$ ma anche $m \mid 5^n-1$

[Gottinger95]

Intanto posto la mia:

Testo nascosto:

Osservazione 1.: Vale \(gcd(5^m-1, 5^n-1) = 4\).
Infatti \(gcd(m,n) = 1 \Leftrightarrow gcd(5^m-1, 5^n-1) = 5^{gcd(m,n)}-1 = 4\)

Osservazione 2. Si ha che \(V_2(5^m-1) = 2\).
Supponiamo per assurdo \(V_2(5^m-1)=\alpha \ge 3\). Per l'osservazione 1 deve valere \(V_2(5^n-1) \le 2\).

Allora, usando il fatto che \(\varphi\) è moltiplicativa e che \(V_2(\varphi(x)) \ge \omega(x)\) per \(x \not \equiv 2 \pmod{4}\), abbiamo:
\(\displaystyle 2 \ge V_2(5^n-1) = V_2(\varphi(5^m-1) ) = V_2 \left (\varphi(2^{\alpha}) \cdot \varphi \left (\frac{5^m-1}{2^{\alpha} } \right ) \right ) = \alpha-1 + V_2 \left (\varphi \left (\frac{5^m-1}{2^{\alpha} } \right ) \right ) \ge \alpha + \omega \left (\frac{5^m-1}{2^{\alpha} } \right ) -1\)
Se \(5^m-1\) non è una potenza di 2, allora
\(\displaystyle 2 \ge V_2(5^n-1) \ge \alpha +\omega \left (\frac{5^m-1}{2^{\alpha} } \right ) -1 \ge \alpha \ge 3\), assurdo.
Se invece è una potenza di 2, abbiamo:
\(\displaystyle 2 \ge V_2(5^n-1) \ge \alpha + \omega \left (\frac{5^m-1}{2^{\alpha} } \right ) -1 = \alpha -1 \ge 2\)
ossia \(\alpha = 3\). Daltronde l'equazione \(5^n-1 = 2^{\alpha} = 8\) non ha soluzione, perciò ciccia.

Osservazione 3. \(m\) è dispari.
Dall'osservazione precedente per LTE abbiamo \(2 = V_2(5^m-1) = 2+ V_2(m) \Rightarrow V_2(m) = 0\), ossia \(m\) dispari.

Osservazione 4. Per ogni \(p : p \mid 5^m-1, p>2\), si ha che \(p^2 \nmid 5^m-1\).
Dal fatto che \(p^2 \mid x \Rightarrow p \mid \varphi(x)\), si avrebbe \(p \mid 5^n-1 = \varphi(5^m-1) \), ossia \(p \mid gcd(5^m-1, 5^n-1) = 4\) con \(p>2\), assurdo.
-------------------------------------------------------------------------------------------
Finalmente abbiamo capito come sono fatti i nostri numeri:
\(\displaystyle 5^m-1 = 4 \prod_{i=1}^k{p_i}\) (1)
\(\displaystyle 5^n-1 = 2 \prod_{i=1}^k{(p_i-1)} \) (2)

Analizzando \(\pmod{p_i}\) la (1) abbiamo
\(5^m \equiv 1 \pmod{p_i} \rightarrow 5^{m+1} \equiv 5\)
e visto che \(m\) è dispari abbiamo \( \left ( \frac{5}{p_i} \right ) = 1\). Per reciprocità quadratica questo implica \( \left ( \frac{p_i}{5} \right ) = 1\), ossia \(p_i \equiv \pm 1 \pmod{5}\).
Se esiste un \(i\) tale che \(p_i \equiv 1 \pmod{5}\), allora analizzando la (2) \(\pmod{5}\) abbiamo \(-1 \equiv 0 \pmod{5}\), assurdo.

Se invece \(p_i \equiv -1 \pmod{5}\) per ogni \(i\), analizzando la (1) \(\pmod{5}\) abbiamo
\( -1 \equiv 4 (-1)^k \pmod{5} \Rightarrow (-1)^k \equiv 1 \pmod{5} \Rightarrow k \equiv 0 \pmod{2}\)

Allora analizzando la (2) \(\pmod{5}\) e considerando che \(2^n \equiv -1 \pmod{5} \Leftrightarrow n \equiv 2 \pmod{4}\):
\(-1 \equiv 2 (-2)^k \equiv (-1)^k \cdot 2^{k+1} \equiv 2^{k+1} \Rightarrow k+1 \equiv 2 \pmod{4} \Rightarrow k \equiv 1 \pmod{2}\)

Assurdo. Con questo si conclude la dimostrazione.
\

[Gottinger95]

Signori, che vi pare, quadra?

[Drago96]

Ma scusa, non c'eri anche tu al PreIMO? xD
Comunque sì, le idee sono quelle (vedere che non ci sono troppi fattori e poi vedendo che il loro numero è sia pari che dispari)

[Gottinger95]

Si, per questo l'ho messo nascosto, ma la soluzione non me la ricordavo! xD

[jordan]

Problema 20 qui