# Modular Arithmetic Equations

I'm trying to solve $x^{16} = [1]_{989}$ in $x ∈\Bbb Z/989\Bbb Z$.

I tried a few simplifications but don't know how to solve it.

Any help is welcome.

-
Do you know the prime factorization of 989? Applying CRT helps. – Jyrki Lahtonen Nov 29 '12 at 15:00
CRT is probably the way to go but not sure how to apply it here. – BrainOverfl0w Nov 29 '12 at 15:03

Here $989=23\cdot 43$, and both $23$ and $43$ are primes. For $x$ to be a solution of your equation, it is necessary and sufficient that $x$ is a solution of the congruence $$x^{16}\equiv 1\pmod{23}$$ and of the congruence $$x^{16}\equiv 1\pmod{43}.$$ For a prime number $p$ the multiplicative group $\mathbb{Z}_p^*$ is cyclic of order $p-1$. In a cyclic group of order $m$ there are $\gcd(m,n)$ solutions of the equation $x^n=1$. From this we can deduce that there are $2=\gcd(23-1,16)$ residue classes $x$ modulo $23$ with the property. You can find them either by trial and error or using DonAntonio's answer as a hint, so I won't do that here. Similar we see that the solutions of the latter congruence form two residue classes modulo $43$.

Now if you know that an integer $x$ is $\equiv a\pmod{23}$ and $\equiv b\pmod{43}$, then the Chinese Remainder Theorem tells you that there is a unique residue class $x$ modulo $989$ such that it satisfies both of the congruences $x\equiv a\pmod{23}$ and $x\equiv b\pmod{43}$. In other words any solution of your congruence modulo $23$ can be paired up with any solution of your congruence modulo $43$. Doing this CRT-pairing for all the four possible pairs will give you four pairwise non-congruent solutions.

If you have problems with any of the steps, ask more.

-
Got it ! Thanks :) – BrainOverfl0w Nov 29 '12 at 15:32

$$x^{16}=1\Longleftrightarrow x^{16}-1=0\Longleftrightarrow (x^8-1)(x^8+1)=0\Longleftrightarrow ...$$

$$\Longleftrightarrow (x-1)(x+1)(x^2+1)(x^4+1)(x^8+1)= 0...$$

-