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

Primitive root question

  1. Jun 11, 2012 #1
    I have a question; Let m have a prime factor [itex] p \equiv 1 (mod 4)[/itex]. Then Euler function [itex]\varphi(m)[/itex] is divisible by 4. Let [itex]x = r^{\varphi(m)}[/itex], then [itex]m|(x^4-1)[/itex] and [itex]x^4-1=(x^2-1)(x^2+1)[/itex]. As [itex]gcd(x^2-1,x^2+1)|2[/itex], either [itex]x^2-1[/itex] or [itex]x^2+1[/itex] is divisible by m. My book says here because of the nature of a prime factor, and that [itex]x^2-1[/itex] isn't divisible by m, so that [itex]x^2+1[/itex] is divisible by m. I cannot understand why [itex]x^2-1[/itex] isn't divisible by m because of "a nature of a prime factor".

    Will anyone help me?

  2. jcsd
  3. Jun 11, 2012 #2

    What is r in [itex]\,x=r^{\varphi(m)}\,[/itex] ? And what book are you reading and where?

    Some conditions must be imposed here: take for example $$\,m=5\,\,,\,r=2\,,\,x=r^{\varphi(m)}=2^4=16 \Longrightarrow 65,525=16^4-1=(16^2-1)(16^2+1)$$but in this case precisely [itex]\,\,5=m\nmid 16^2+1=257\,\,[/itex] , but rather [itex]\,\,5=m\mid 16^2-1=255\,\,[/itex] , contradicting what you wrote.

  4. Jun 11, 2012 #3
    Thank you for your reply.

    r is a primitive root for m. Sorry I wrote "primitive factor" because I didn't know the math nomenclature (I'm Japanese in Japan). This is a Japanese book for preparation for IMO. I'm too old for IMO, but just interested in it and reading. My 1st daughter was chosen as a Japanese representative for CGMO(China Girl's Math Olympiad).

    I have made two mistakes in the previous message; my book says m is "a power of prime number" p, where [itex]p\equiv 1 (mod 4)[/itex]. (but this is not a big mistake).

    The other main mistake is [itex]x=r^\frac{\varphi(m)}{4}[/itex] (so [itex]p\equiv 1 (mod 4)[/itex] is necessary). So in your case, [itex] x ≠ 16[/itex]. x had to be (or could be) 2 and [itex]m|x^4-1=15=(x^2-1)(x^2+1).[/itex] It makes sense. x=r can be 3.

    Sorry for mistakes.
    Last edited: Jun 12, 2012
  5. Jun 12, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Since r is a primitive root of m = pk, the values [itex]r, r^{2}, r^{3}, ... r^{\phi(m)}[/itex], modulo m, are distinct. In particular, [itex]r^{\phi(m)}\equiv1 (m)[/itex], and no power of r from 1 to [itex]\phi(m)-1[/itex] can satisfy that. [itex]x^{2} = r^{\phi(m)/2}[/itex], so [itex]x^{2} \neq 1 (m)[/itex]
    (Latex doesn't seem to have a \nequiv symbol.)
  6. Jun 12, 2012 #5

    Try [itex]\rlap{\,/}{\equiv}[/itex] to negate the equivalence sign.

  7. Jun 12, 2012 #6
    Thank you! I've got the idea.

  8. Jun 12, 2012 #7


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook