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!