1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Primitive root question
  1. Root question (Replies: 5)