Residuo h-uplo modulo n

Un numero \( m \) è un residuo \( h \)-uplo modulo \( n \) se l'equazione \[ x^h \equiv m \pmod{n}\] ha una soluzione intera \( x \).

In altre parole, significa che esiste almeno un numero \( x \) che elevato alla potenza \( h \) dia un resto di \( m \) quando diviso per \( n \).

Come capire se m è un residuo di h modulo n?

Un intero \( m \) è un residuo \( h \)-uplo modulo \( n \) quando

$$ m^{\varphi(n)/d} \equiv 1 \pmod{n} $$

Dove :

• \( n \) è un numero intero positivo.
• \( m \) è coprimo con \( n \) cioè i due numeri non hanno divisori in comune \( MCD(m, n) = 1 \)).
• \( n \) ha una radice primitiva \( r \).
• \( d \) è il MCD (massimo comune divisore) tra \( h \) e \( \varphi(n) \), cioè \( d = \gcd(h, \varphi(n)) \)

Questo significa che se elevo \( m \) alla potenza \( \varphi(n)/d \), ottengo 1 modulo \( n \).

Quante sono le soluzioni? Se l'equazione \( x^h \equiv m \pmod{n} \) ha soluzioni, allora ha esattamente \( d \) soluzioni incongrue modulo \( n \).

Un esempio pratico

Devo verificare se \( m=4 \) è un residuo \( h =2 \) nel modulo \( n= 7 \)

\[ x^2 \equiv 4 \pmod{7} \]

Calcolo la funzione di Eulero che restituisce il numero di coprimi di 7.

\[ \varphi(7) = 6 \]

In questo caso ci sono sei numeri coprimi da 1 a 7. Del resto 7 è un numero primo, quindi tutti i numeri da 1 a 7 non hanno divisori comuni con 7.

Calcolo il massimo comune divisore tra \( h=2 \) e \( \varphi(n)=6 \).

$$ d = MCD(h, \varphi(n)) $$

$$ d = MCD(2,6) = 2 $$

Devo verificare se:

\[ m^{\varphi(n)/d} \equiv 1 \pmod{n} \]

\[ 4^{\varphi(7)/2} = 4^{6/2} = 4^3 \equiv 1 \pmod{7} \]

Sapendo che \( 4^3 = 64 \equiv 1 \mod 7 \) la condizione è soddisfatta.

\[4^3 = 64 \equiv 1 \pmod{7}\]

Poiché la condizione è soddisfatta, l’equazione \( x^2 \equiv 4 \pmod{7} \) ha esattamente \( d = 2 \) soluzioni incongrue modulo 7.

Quali sono le soluzioni della variabile x?

Ora devo trovare le soluzioni \( x \) tali che:

\[ x^2 \equiv 4 \pmod{7} \]

Provo i numeri da 0 a 6:

• \( 0^2 = 0 \)
• \( 1^2 = 1 \)
• \( 2^2 = 4 \equiv 4 \pmod{7} \) ✅
• \( 3^2 = 9 \equiv 2 \pmod{7} \)
• \( 4^2 = 16 \equiv 2 \pmod{7} \)
• \( 5^2 = 25 \equiv 4 \pmod{7} \) ✅
• \( 6^2 = 36 \equiv 1 \pmod{7} \)

Le soluzioni sono quindi:

\[ x \equiv 2, 5 \pmod{7} \]

In conclusione, l’equazione \( x^2 \equiv 4 \pmod{7} \) ha esattamente 2 soluzioni incongrue: \( x \equiv 2 \) e \( x \equiv 5 \) modulo 7.

Quindi, 4 è un residuo 2-plo modulo 7.

Note

Alcune note aggiuntive sull'argomento

• Se \( m = 1 \), l’equazione \( x^h \equiv 1 \pmod{n} \) ha esattamente \( d = \gcd(h, \varphi(n)) \) soluzioni incongrue modulo \( n \).

  Questo significa che esistono esattamente \( d \) valori distinti di \( x \) che soddisfano l’equazione. Il numero di soluzioni dipende da come \( h \) e \( \varphi(n) \) condividono fattori comuni.
  Esempio. Considero il caso di \( m = 1 \) per risolvere l'equazione $$ x^4 \equiv 1 \pmod{21} $$ Dove $ h= 4 $. Poiché \( 21 = 3 \times 7 \) è un numero composto da due fattori primi ( $ n_1=3 $ e $ n_2 = 7 $ ) posso calcolare la funzione di Eulero usando la formula $ \varphi(n) = (n_1 - 1) \cdot (n_2 - 1) $ \[ \varphi(21) = (3-1) \cdot (7-1) = 2 \cdot 6 = 12 \] Quindi, il numero $ 21 $ ha $ 12 $ numeri coprimi tra 1 e 21. Calcolo il massimo comune divisore tra \( h = 4 \) e \( \varphi(21) = 12 \) $$ d = MCD(h, \varphi(n)) = MCD(4, 12) = 4 $$ Dunque, mi aspetto $ d=4 $ soluzioni incongrue modulo 21 per l'equazione \( x^4 \equiv 1 \pmod{21} \). Provo a calcolare le potenze di alcuni numeri modulo 21.

  • \( 1^4 \equiv 1 \pmod{21} \) ✅
  • \( 2^4 \equiv 16 \pmod{21} \)
  • \( 3^4 \equiv 18 \pmod{21} \)
  • \( 4^4 \equiv 4 \pmod{21} \)
  • \( 5^4 \equiv 16 \pmod{21} \)
  • \( 6^4 \equiv 15 \pmod{21} \)
  • \( 7^4 \equiv 7 \pmod{21} \)
  • \( 8^4 \equiv 1 \pmod{21} \) ✅
  • \( 9^4 \equiv 9 \pmod{21} \)
  • \( 10^4 \equiv 4 \pmod{21} \)
  • \( 11^4 \equiv 4 \pmod{21} \)
  • \( 12^4 \equiv 9 \pmod{21} \)
  • \( 13^4 \equiv 1 \pmod{21} \) ✅
  • \( 14^4 \equiv 7 \pmod{21} \)
  • \( 15^4 \equiv 15 \pmod{21} \)
  • \( 16^4 \equiv 16 \pmod{21} \)
  • \( 17^4 \equiv 4 \pmod{21} \)
  • \( 18^4 \equiv 18 \pmod{21} \)
  • \( 19^4 \equiv 16 \pmod{21} \)
  • \( 20^4 \equiv 1 \pmod{21} \) ✅

  Quindi, le soluzioni incongrue modulo 21 dell'equazione \( x \equiv 1 \pmod{21} \) sono effettivamente quattro: \( x \equiv 1, 8, 13, 20 \pmod{21} \)

• Se \( m = -1 \) e l’equazione \( x^h \equiv -1 \pmod{n} \) ha soluzioni, allora il numero di soluzioni incongrue è esattamente \( d = \gcd(h, \varphi(n)) \), a condizione che \( n \) sia dispari e \( h \) sia pari.

  Questo significa che, in questi casi particolari, esistono esattamente \( d \) valori distinti di \( x \) che soddisfano l’equazione. Tuttavia, questo corollario non garantisce sempre l'esistenza di soluzioni. Ad esempio, se \( n \) è pari o \( h \) è dispari, l’equazione potrebbe non essere risolvibile. Inoltre, anche se \( h \) è pari e \( n \) è dispari, l'equazione può comunque non avere soluzioni se \(-1\) non è un residuo biquadratico modulo \( n \), come accade per \( n = 21 \).
  Esempio. Considero il caso di \( m = -1 \) nell'equazione dell'esempio precedente $$ x^4 \equiv 1 \pmod{21} $$ Dove $ h= 4 $ è pari e $ n=21 $ è dispari. Senza ricalcolare nulla, so già che \( \varphi(21) = 12 \) e il massimo comune divisore tra \( h = 4 \) e \( \varphi(21) = 12 \) $$ d = MCD(h, \varphi(n)) = MCD(4, 12) = 4 $$ Dunque, mi aspetto che ci siano $ d=4 $ soluzioni incongrue modulo 21 per l'equazione \( x^4 \equiv -1 \pmod{21} \). Tuttavia -1 non è un residuo biquadratico di 21 e non ci sono soluzioni che restituisco $ x^h  = -1 \equiv 20 \pmod{21} $
  Esempio. Considero il caso di \( m = -1 \) per risolvere l'equazione $$ x^4 \equiv -1 \pmod{17} $$ Dove $ h= 4 $. Poiché \( 17 \) è un numero primo, la funzione di Eulero è $ \varphi(17) = (17-1)= 16 $ poiché, il numero $ 17 $ ha $ 16 $ numeri coprimi tra 1 e 17. Calcolo il massimo comune divisore tra \( h = 4 \) e \( \varphi(17) = 16 \) $$ d = MCD(h, \varphi(n)) = MCD(4, 16) = 4 $$ Dunque, mi aspetto che ci siano $ d=4 $ soluzioni incongrue modulo 17 per l'equazione \( x^4 \equiv -1 \pmod{21} \). Provo a calcolare le potenze biquadratiche dei numeri nel modulo 17.

  • \( 1^4 \equiv 1 \pmod{17} \)
  • \( 2^4 \equiv 16 \equiv -1 \pmod{17} \) ✅
  • \( 3^4 \equiv 13 \pmod{17} \)
  • \( 4^4 \equiv 1 \pmod{17} \)
  • \( 5^4 \equiv 13 \pmod{17} \)
  • \( 6^4 \equiv 4 \pmod{17} \)
  • \( 7^4 \equiv 4 \pmod{17} \)
  • \( 8^4 \equiv 16 \equiv -1 \pmod{17} \) ✅
  • \( 9^4 \equiv 16 \equiv -1 \pmod{17} \) ✅
  • \( 10^4 \equiv 4 \pmod{17} \)
  • \( 11^4 \equiv 4 \pmod{17} \)
  • \( 12^4 \equiv 14 \pmod{17} \)
  • \( 13^4 \equiv 1 \pmod{17} \)
  • \( 14^4 \equiv 13 \pmod{17} \)
  • \( 15^4 \equiv 16 \equiv -1 \pmod{17} \) ✅
  • \( 16^4 \equiv 1 \pmod{17} \)

  Quindi, le soluzioni incongrue dell'equazione \( x \equiv -1 \pmod{17} \) sono effettivamente quattro: \( x \equiv 2, 8, 9, 15 \pmod{21} \)

E così via.