Congruenta pt. orice întreg mod numere de o forma

[Filip Chindea]

Sa se gaseasca primele \( p \) si \( q \) astfel încât pentru toti întregii \( a \) are loc \( a^{3pq} - a \equiv 0 \pmod{3pq} \).

Romania TST 1996, Ziua 3, Problema 3

[Filip Chindea]

Sa se gaseasca primele \( p \) si \( q \) astfel încât pentru toti întregii \( a \) are loc \( a^{3pq} - a \equiv 0 \pmod{3pq} \).

Romania TST 1996, Ziua 3, Problema 3

La solicitarea lui SNT voi posta (de altfel evidenta) o solutie clasica, sarind peste câteva verificari "by hand".
Fara restrângere de generalitate, \( p \le q \). Fie acum \( a \) o radacina primitiva \( \pmod{q} \). Din Mica Teorema a lui Fermat, \( a \equiv a^{3pq} \equiv (a^q)^{3p} \equiv a^{3p} \pmod{p} \), si astfel \( a^{3p - 1} \equiv 1 \pmod{q} \). De aici \( q - 1 = \varphi(q) = \mathrm{ord}_q(a) | 3p - 1 \). Concluzionam analog si \( p - 1 | 3q - 1 \).
Fie \( \frac{3p-1}{q-1} = s \), \( \frac{3q-1}{p-1} = t \), cu \( s, t \in \mathbb{N}^{\ast} \). Pentru \( p \ge 3 \), de asemenea \( q \ge 3 \). Astfel \( s = \frac{3p - 1}{q - 1} \le \frac{3q - 1}{q - 1} \le \frac{3q - 1 + q - 3}{q - 1} = 4 \). Pentru \( s = 1 \), \( q = 3p \) prim - fals. Daca \( s = 2 \), \( q = \frac{3p + 1}{2} \) si \( p - 1 | 6q - 2 = 9p + 1 \), avem \( (p, q) \in \{ (3, 5); (11, 17) \} \). In primul caz derivam o contradictie pentru \( a = 2 \). Daca \( s = 3 \), \( 3p - 1 = 3(q - 1) \), fals, iar \( s = 4 \) conduce la \( p - 1 | 12q - 4 = 9p + 5 \) iar \( p = q = 3 \), din nou fals luând \( a = 2 \).
Daca se întâmpla ca \( p = 2 \), din conditia \( q - 1 | 3p - 1 = 5 \) deducem \( q = 2 \), de asemenea în contradictie cu ipoteza pentru \( a = 2 \).
Mai ramâne \( \{ p, q \} = \{ 11, 17 \} \), pentru care într-adevar ipoteza se verifica.

Remarca. Numim Carmichael orice numar compus, impar si de asemenea pseudoprim Fermat în orice baza \( a \) - întreg pozitiv. Are loc criteriul

[Korselt] Avem \( n \) Carmichael \( \Leftrightarrow n \) liber de patrate, si pentru orice prim \( p | n \), de asemenea \( p - 1 | n - 1 \).

De aici se concluzioneaza usor ca orice astfel de \( n \) are cel putin \( 3 \) factori primi distincti, ceea ce se întâmpla si cu cel mai mic astfel de numar cunoscut, adica exact cel din problema - \( 561 = 3 \cdot 11 \cdot 17 \).
Mai multe detalii, generale sau tehnice, gasiti aici.