Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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...$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.