Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 1, 2005 #1
    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
     
  2. jcsd
  3. Dec 1, 2005 #2

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    If x = 3 and n = 3 then [itex]x^n - 2 = 25 = 5^2[/itex] so your assertion appears to be false.
     
  4. Dec 1, 2005 #3
    Oops sorry - I forgot to add n is even
     
  5. Dec 1, 2005 #4
    WHERE DID THE N COME FROM? The simple fact is that all odd squares ae congruent to 1 Mod 8.
     
  6. Dec 1, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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 arguement helps, or am i missing something obvious?
     
  7. Dec 1, 2005 #6

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Big hint: think quadratic residues.
     
  8. Dec 1, 2005 #7
    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.
     
  9. Dec 1, 2005 #8

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Dec 1, 2005 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper


    It's not the number, but its factors.
     
  11. Dec 1, 2005 #10
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruences of (x^n-2) and its factors
Loading...