Congruences of (x^n-2) and its factors

[AntonVrba]

It is easy to show that for all odd x that:
(x^n-2) = 7 (mod 8)

but why are the factors of above either congruent 1 or 7 modula 8, i.e
factor(x^n-2) = {1,7} (mod 8)

can anyone give me a hint.

regards
Anton

 

[Tide]

If x = 3 and n = 3 then x^n - 2 = 25 = 5^2 so your assertion appears to be false.

 

[AntonVrba]

Oops sorry - I forgot to add n is even

 

[robert Ihnot]

WHERE DID THE N COME FROM? The simple fact is that all odd squares ae congruent to 1 Mod 8.

 

[matt grime]

The question is asking for more than that, it even starts by observing that x^n-2 is trivally -1 mod 8. it then asks you to show that all factors of x^n-2 are then either plus or minus 1 mod 8 which is a little bit trivcky, I think.

My inital reaction is that this seems as though it might be false, small counter examples seem to satisfy the proposition, so my initial reaction might be wrong.

if indeed it is true, then my first observation is it suffices to prove this for n=2 and all odd x: if the conjecture is true, this is a special case of it, and if it is true for n=2 then one can deduce the conjecture by noting that x^{2m}=(x^m)^2

however, even then nothing obvious springs to mind

x^2-2 = (x-1)(x+1) - 1 but i don't see that it reall helps.

perhaps some reduction argument helps, or am i missing something obvious?

 

[shmoe]

Big hint: think quadratic residues.

 

[robert Ihnot]

I must be missing something. Since he is talking about odd squares, X^n-2, X is odd, n is even, we know that all odd squares are congruent to 1 Mod 8. So that if we subtract 2 it is congruent to -1==7 Mod 8.

If the algebra is a problem, all you have to do is look at the cases of X==1,3,5,7. This is four cases.

By induction if X^2 ==1 Mod 8, we look at (X+2)^2 ==X^2+4X+4 ==1+4(X+1), since (X+1) is even 4(X+1) ==0 Mod 8.

 

[shmoe]

It's a question about the factors of x^n-2. e.g. 11^2-2=119. Then the factors of 119 are 1, 7, 17 and 119, all are congruent to 1 or 7 mod 8.

 

[matt grime]

I must be missing something.

It's not the number, but its factors.

 

[robert Ihnot]

O.K. I got it. X^2=2 Mod p has a solution obtained by quadratic reciprocity. See http://en.wikipedia.org/wiki/Quadratic_reciprocity