Quasi Fermat

[jordan]

Trovare tutte le coppie di primi $(p,q)$ tali che se $m$ è intero allora \[ 3pq \mid m^{3pq}-m \]


(TST Romania 96)

[karlosson_sul_tetto]

Intero, intero positivo o la cipolla?


EDIT: ok, non mi pare influisca troppo ma preferisco lasciare la domanda

[Leonida]

Lemma: siano $p,q > 3$ due primi distinti. Allora esiste un generatore modulo $p$ coprimo con 3 e $q$.
Dim.: sia $g_0$ un generatore modulo $p$. Considero il seguente sistema di congruenze:
\[
\left\{
\begin{array}{l}
g \equiv g_0 \pmod p \\
g \equiv 1 \pmod q \\
g \equiv 1 \pmod 3
\end{array}
\right.
\]
Esso ammette soluzione per il Teorema Cinese, e detta $g$ una qualunque soluzione, $g$ genera modulo $p$ ed è coprimo con 3 e $q$.
La divisibilità deve valere $\forall m \in \mathbb{Z}$: considero in particolare un $m$ t.c. $(m, 3pq) = 1$. Deve valere:
\[
\left\{
\begin{array}{l}
3 \mid m^{3pq -1} -1 \\
p \mid m^{3pq -1} -1 \\
q \mid m^{3pq -1} -1
\end{array}
\right.
\]
Scelgo $m \equiv 2 \pmod 3$, coprimo con $p$ e $q$ (l'esistenza mi è assicurata dal Teorema Cinese): la prima divisibilità equivale a
\[
m^{3pq -1} -1 \equiv 0 \pmod 3 \Leftrightarrow 2^{3pq -1} -1 \equiv 0 \pmod 3
\]
da cui deduco che $p,q$ devono essere dispari. Inoltre riscrivo la seconda divisibilità come:
\[
m^{3pq -1} -1 \equiv 0 \pmod p \Leftrightarrow (m^{3q})^p \cdot m^{-1} \equiv 1 \pmod p \Leftrightarrow m^{3q -1} \equiv 1 \pmod p
\]
Analogamente, la terza divisibilità equivale a $m^{3p -1} \equiv 1 \pmod q$.
Ora se $p=3$, ottengo $m^8 \equiv 1 \pmod q$. In particolare prendo $m$ generatore modulo $q$: nonostante io sia limitato dal vincolo di $(m, 3pq) = 1$, grazie al Lemma posso operare questa scelta. Segue che $q-1 \mid 8$, e le uniche scelte possibili sono $q=3$ e $q=5$, da cui $3pq = 27$ o $3pq = 45$. In entrambi i casi la divisibilità iniziale non è verificata da $m=2$.
Ora considero WLOG $5 \leq p \leq q$, deve valere:
\[
\left\{
\begin{array}{l}
m^{3q -1} \equiv 1 \pmod p \\
m^{3p -1} \equiv 1 \pmod q
\end{array}
\right.
\]
Prendo in particolare un $m$ generatore modulo $q$ (posso, come già detto prima) e ottengo che $q-1 \mid 3p -1$: ma poichè $q \geq p$, le uniche possibilità sono $q-1 = 3p -1$ e $q-1 = \frac{3p -1}{2}$. Dalla prima ottengo $q = 3p$, che non è accettabile in quanto $q$ non risulta primo; dalla seconda ottengo $q= \displaystyle \frac{3p +1}{2}$, che risulta quindi l'unica scelta possibile. Sostituendo nella prima congruenza del sistema, trovo $\displaystyle m^{\displaystyle \frac{9p +1}{2}} \equiv 1 \pmod p $.
Questa deve essere verificata $\forall m \in \mathbb{Z}$, con $(m,3pq) =1$. Ancora grazie al Lemma, scelgo $m$ generatore modulo $p$ e ottengo
\[
p-1 \mid \frac{9p +1}{2} \Leftrightarrow 2p -2 \mid 9p +1
\]
Ma
\[
\frac{9p +1}{2p -2} = \frac{9p -9 +10}{2p -2} = \frac{9}{2} + \frac{10}{2p -2}
\]
e il secondo addendo è strettamente compreso tra 0 e $\displaystyle \frac{10}{8}$. Segue che l'unico valore intero che può assumere $\displaystyle \frac{9p +1}{2p -2}$ è 5, che si ottiene per $p=11$ e da cui ricavo $q=17$. E' facile verificare con il Piccolo Teorema di Fermat che la terna $(3,11,17)$ funziona, e per quanto detto è l'unica.

Spero di non aver preso abbagli! Jordan, tu come l'avevi risolto?

[jordan]

Finalmente ho trovato il tempo di leggermela per bene, sorry for the delay.

Lemma: siano $p,q > 3$ due primi distinti. Allora esiste un generatore modulo $p$ coprimo con 3 e $q$.

Penso tu intenda in $\mathbb{Z} \cap [1,3pq]$, comunque sì, funziona.

Ora considero WLOG $5 \leq p \leq q$

Sbaglio o hai saltato il caso $p=q=3$? Per applicare il lemma sopra avevi come ipotesi che $p,q$ erano distinti..

Questa deve essere verificata $\forall m \in \mathbb{Z}$, con $(m,3pq)$.

$(m,3pq)=1$?

Spero di non aver preso abbagli! Jordan, tu come l'avevi risolto?

Non mi pare che ci siano strade piu' ovvie e/o veloci di quella tua

[Leonida]

Ok
Sì, voleva essere un $(m, 3pq) =1$, ora modifico! Comunque $p=q=3$ l'avevo trattato a parte, con $m=2$ si vede che non funziona.

[jordan]

Comunque $p=q=3$ l'avevo trattato a parte, con $m=2$ si vede che non funziona.

Allora, bene