Solve Euler's Equation x^7 ≡ 21 mod 66

[Hummingbird25]

Hi

How do I solve the equation x^7 \equiv 21 modulo 66

66 = 2.3.11 so try solving it mod 3 and mod 11 (mod 2 doesn't gives any new information). This tells us x is divisible mod 3, and x^7 = -1 mod 11. One solution to this is x = -1 mod 7. The smallest solution of these two congruences is x=21, so this seems like a good guess.

Now notice that 21*21 = 3.7 (2.11 - 1) = 7.66 - 3.7 = -21 mod 66
So 21 ^n = 21. (-1)^n mod 66. Therefore x=21 is a solution of the equation. There may be more however...

Sincerely Yours
Hummingbird25

 

[mighty2000]

Hello Hummingbird25,

Thank you for your question. Solving equations in modular arithmetic can be tricky, but with some careful steps, we can find a solution.

First, let's rewrite the equation as x^7 - 21 = 0 (mod 66). This means that x^7 - 21 is divisible by 66, or in other words, it is a multiple of 66.

Next, we can factor the left side of the equation as (x - 21)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1). This means that either (x - 21) or (x^6 + x^5 + x^4 + x^3 + x^2 + x + 1) must be divisible by 66.

Since 66 = 2*3*11, we can use the Chinese Remainder Theorem to solve the equation in mod 3 and mod 11 separately.

In mod 3, we have x^7 - 21 = 0 (mod 3). This means that x^7 is congruent to 21 (mod 3). Since 21 is not divisible by 3, x must be divisible by 3. Therefore, x = 3k for some integer k.

In mod 11, we have x^7 - 21 = 0 (mod 11). This means that x^7 is congruent to 21 (mod 11). We can rewrite 21 as -1 (mod 11), so x^7 is congruent to -1 (mod 11). By Fermat's Little Theorem, we know that x^10 is congruent to 1 (mod 11) for any integer x not divisible by 11. Therefore, x^70 is congruent to 1 (mod 11). This means that x^7 is congruent to 1 (mod 11) or -1 (mod 11). Since we already know that x is divisible by 3, we can eliminate the possibility of x being congruent to 1 (mod 11). Therefore, x must be congruent to -1 (mod 11).

Combining the results from mod 3 and mod 11, we get x = 3k - 1 for some integer k.

Now, let's try plugging in some values for