Why Isn't x^2-1 Divisible by m?

[maverick6664]

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

Will anyone help me?

TIA

 

[DonAntonio]

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

Will anyone help me?

TIA

What is r in \,x=r^{\varphi(m)}\, ? 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 \,\,5=m\nmid 16^2+1=257\,\, , but rather \,\,5=m\mid 16^2-1=255\,\, , contradicting what you wrote.

DonAntonio

 

[maverick6664]

What is r in \,x=r^{\varphi(m)}\, ? 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 \,\,5=m\nmid 16^2+1=257\,\, , but rather \,\,5=m\mid 16^2-1=255\,\, , contradicting what you wrote.

DonAntonio

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 p\equiv 1 (mod 4). (but this is not a big mistake).

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

Sorry for mistakes.

 

[haruspex]

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

 

[DonAntonio]

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

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

DonAntonio

 

[maverick6664]

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

Thank you! I've got the idea.

-Tetsuji

 

[haruspex]

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

Thanks!