hth Power Residue Modulo n
A number \( m \) is an \( h \)th power residue modulo \( n \) if the equation \[ x^h \equiv m \pmod{n} \] has at least one integer solution \( x \).
In other words, this means there exists some integer \( x \) such that when raised to the power of \( h \), it leaves a remainder of \( m \) when divided by \( n \).
How can we determine if \( m \) is an \( h \)th power residue modulo \( n \)?
An integer \( m \) is an \( h \)th power residue modulo \( n \) if:
$$ m^{\varphi(n)/d} \equiv 1 \pmod{n} $$
Where:
- \( n \) is a positive integer.
- \( m \) is coprime to \( n \), meaning they have no common divisors (i.e., \( \gcd(m, n) = 1 \)).
- \( n \) has a primitive root \( r \).
- \( d \) is the greatest common divisor (gcd) of \( h \) and \( \varphi(n) \), i.e., \( d = \gcd(h, \varphi(n)) \).
In simpler terms, raising \( m \) to the power of \( \varphi(n)/d \) must result in 1 modulo \( n \).
How many solutions are there? If the equation \( x^h \equiv m \pmod{n} \) has solutions, then it has exactly \( d \) incongruent solutions modulo \( n \).
A Practical Example
Let’s determine whether \( m=4 \) is a quadratic residue (i.e., a 2nd power residue) modulo \( n=7 \).
\[ x^2 \equiv 4 \pmod{7} \]
First, we compute Euler’s totient function, which counts the numbers that are coprime to 7:
\[ \varphi(7) = 6 \]
Since 7 is a prime number, all numbers from 1 to 6 are coprime to it.
Next, we find the greatest common divisor of \( h=2 \) and \( \varphi(n)=6 \):
$$ d = \gcd(h, \varphi(n)) $$
$$ d = \gcd(2,6) = 2 $$
Now, we check if the following condition holds:
\[ m^{\varphi(n)/d} \equiv 1 \pmod{n} \]
\[ 4^{\varphi(7)/2} = 4^{6/2} = 4^3 \equiv 1 \pmod{7} \]
Since \( 4^3 = 64 \equiv 1 \pmod{7} \), the condition is satisfied.
\[ 4^3 = 64 \equiv 1 \pmod{7} \]
Therefore, the equation \( x^2 \equiv 4 \pmod{7} \) has exactly \( d = 2 \) incongruent solutions modulo 7.
What are the possible values of \( x \)?
Now, let’s find the values of \( x \) that satisfy:
\[ x^2 \equiv 4 \pmod{7} \]
We check the squares of numbers from 0 to 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} \)
Thus, the solutions are:
\[ x \equiv 2, 5 \pmod{7} \]
In conclusion, the equation \( x^2 \equiv 4 \pmod{7} \) has exactly two distinct solutions: \( x \equiv 2 \) and \( x \equiv 5 \) modulo 7.
Therefore, 4 is a quadratic residue modulo 7.
What does "incongruent solutions" mean? When we say an equation has incongruent solutions modulo \( n \), it means the solutions are distinct modulo \( n \), meaning they yield different remainders when divided by \( n \). In other words,
$$ a \not \equiv b \pmod{n} $$
If they were congruent, they would be considered the same solution. For example, in the equation
\[ x^2 \equiv 4 \pmod{7} \]
We found two solutions, \( x = 2 \) and \( x = 5 \), both of which satisfy the equation:
- \( 2^2 = 4 \equiv 4 \pmod{7} \) ✅
- \( 5^2 = 25 \equiv 4 \pmod{7} \) ✅
Two numbers are congruent modulo 7 if their difference is a multiple of 7, meaning:
\[ 2 - 5 = -3 \]
Since \(-3\) is not a multiple of 7, the numbers 2 and 5 are not congruent modulo 7, which means they are incongruent solutions.
$$ 2 \not \equiv 5 \pmod{7} $$
Notes
Some additional insights on the topic
-
If \( m = 1 \), the equation \( x^h \equiv 1 \pmod{n} \) has exactly \( d = \gcd(h, \varphi(n)) \) distinct solutions modulo \( n \).
In other words, there are precisely \( d \) different values of \( x \) that satisfy the equation. The number of solutions depends on the common factors shared by \( h \) and \( \varphi(n) \).Example. Let’s take the case where \( m = 1 \) and solve the equation: $$ x^4 \equiv 1 \pmod{21} $$ Here, \( h = 4 \). Since \( 21 = 3 \times 7 \) is a composite number with two prime factors ( \( n_1 = 3 \) and \( n_2 = 7 \) ), we can determine Euler’s totient function using the formula: \[ \varphi(n) = (n_1 - 1) \cdot (n_2 - 1) \] \[ \varphi(21) = (3-1) \cdot (7-1) = 2 \times 6 = 12 \] So, there are 12 integers between 1 and 21 that are coprime to 21. Now, let’s compute the greatest common divisor between \( h = 4 \) and \( \varphi(21) = 12 \): $$ d = \gcd(h, \varphi(n)) = \gcd(4, 12) = 4 $$ This tells us that we should expect \( d = 4 \) incongruent solutions modulo 21 for the equation \( x^4 \equiv 1 \pmod{21} \). Let’s verify by computing the fourth power of several numbers 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} \) ✅
-
If \( m = -1 \) and the equation \( x^h \equiv -1 \pmod{n} \) has solutions, then the number of distinct incongruent solutions is exactly \( d = \gcd(h, \varphi(n)) \), provided that \( n \) is odd and \( h \) is even.
In other words, under these specific conditions, there are exactly \( d \) distinct values of \( x \) that satisfy the equation. However, this corollary does not guarantee that solutions always exist. For instance, if \( n \) is even or \( h \) is odd, the equation may not have any solutions at all. Furthermore, even when \( h \) is even and \( n \) is odd, the equation can still be unsolvable if \(-1\) is not a biquadratic residue modulo \( n \), as is the case when \( n = 21 \).Example. Let's consider the case where \( m = -1 \) in the equation from the previous example: $$ x^4 \equiv -1 \pmod{21} $$ Here, \( h = 4 \) is even, and \( n = 21 \) is odd. Without recalculating anything, we already know that \( \varphi(21) = 12 \) and that the greatest common divisor between \( h = 4 \) and \( \varphi(21) = 12 \) is: $$ d = \gcd(h, \varphi(n)) = \gcd(4, 12) = 4 $$ Based on this, we would expect \( d = 4 \) distinct incongruent solutions modulo 21 for the equation \( x^4 \equiv -1 \pmod{21} \). However, since -1 is not a biquadratic residue modulo 21, no values of \( x \) satisfy \( x^4 \equiv -1 \equiv 20 \pmod{21} \).Example. Now, let’s examine the case where \( m = -1 \) in the equation: $$ x^4 \equiv -1 \pmod{17} $$ Here, \( h = 4 \). Since \( 17 \) is a prime number, Euler’s totient function is given by: $$ \varphi(17) = 17 - 1 = 16 $$ meaning there are 16 integers between 1 and 17 that are coprime to 17. We now compute the greatest common divisor between \( h = 4 \) and \( \varphi(17) = 16 \): $$ d = \gcd(h, \varphi(n)) = \gcd(4, 16) = 4 $$ So, we expect \( d = 4 \) distinct incongruent solutions modulo 17 for the equation \( x^4 \equiv -1 \pmod{17} \). Let’s verify this by computing the fourth powers of several numbers 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} \)
And that’s it!
