2
$\begingroup$

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.

  • 0
    CRT is probably the way to go but not sure how to apply it here.2012-11-29

2 Answers 2

2

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.

  • 0
    Got it ! Thanks :)2012-11-29
0

$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...$