Co-prime challenge

[Poirot]

Let n =xy be a positive integer where x,y>2 are co-prime. Show that if a is co-prime to n, then $a^{\frac{\phi(n)}{2}}=1$ mod(n)

 

[Bacterius]

Re: co-prime challenge

Spoiler

[JUSTIFY]$$a^{\frac{\varphi{(n)}}{2}} \equiv b \pmod{n} ~ ~ ~ ~ \iff ~ ~ ~ ~ a^{\frac{\varphi{(n)}}{2}} \equiv b \pmod{x} ~ ~ ~ ~ \iff ~ ~ ~ ~ a^{\varphi{(x)} \frac{\varphi{(y)}}{2}} \equiv b \pmod{x} ~ ~ ~ ~ \implies ~ ~ ~ ~ b = 1$$
Explanations and justifications below:


Step 1: Apply the CRT, since $n = xy$.
Step 2: Definition of the totient function, and $\gcd{(x, y)} = 1$.
Step 3: Recall $\varphi{(y)}$ is even as $y > 2$. Use Euler's Theorem as $\gcd{(a, x)} = 1$.

It occurs to me I've been using the parity property of $\varphi$ an inordinate number of times in the past week [/JUSTIFY]

 

[Poirot]

Re: co-prime challenge

Spoiler

[JUSTIFY]$$a^{\frac{\varphi{(n)}}{2}} \equiv b \pmod{n} ~ ~ ~ ~ \iff ~ ~ ~ ~ a^{\frac{\varphi{(n)}}{2}} \equiv b \pmod{x} ~ ~ ~ ~ \iff ~ ~ ~ ~ a^{\varphi{(x)} \frac{\varphi{(y)}}{2}} \equiv b \pmod{x} ~ ~ ~ ~ \implies ~ ~ ~ ~ b = 1$$
Explanations and justifications below:


Step 1: Apply the CRT, since $n = xy$.
Step 2: Definition of the totient function, and $\gcd{(x, y)} = 1$.
Step 3: Recall $\varphi{(y)}$ is even as $y > 2$. Use Euler's Theorem as $\gcd{(a, x)} = 1$.

It occurs to me I've been using the parity property of $\varphi$ an inordinate number of times in the past week [/JUSTIFY]

Your method is better than mine. But in step 1, wouldn't the CRT be applicable if n and x were co-prime? As it is, the -> direction is clear, but how do you get the <- drection in step 1?

 

[Bacterius]

Re: co-prime challenge

Your method is better than mine. But in step 1, wouldn't the CRT be applicable if n and x were co-prime? As it is, the -> direction is clear, but how do you get the <- drection in step 1?

[JUSTIFY]Yes, that is a good point. What is missing is that the step has to follow for both $x$ and $y$ for the equivalence to be fully satisfied (the argument is valid for both factors, so it does hold). Good catch! I guess one could slip a WLOG in there somewhere..[/JUSTIFY]

 

[Poirot]

Re: co-prime challenge

By euler's theorem, $a^{\phi(n)}=1$ mod (n). Since n>2, phi(n) is even so that

$a^{{\frac{\phi(n)}{2}}^2}=1$ mod(n)

Thus, $|a^{\frac{\phi(n)}{2}}|=1$ mod(n)

Towards a contradiction, assume $a^{\frac{\phi(n)}{2}}=-1$ mod(n)

-> $a^{\frac{\phi(x)\phi(y)}{2}}=-1$ mod(x) using the multiplicative property of phi and the fact that any multiple of n is a multiple of x also.

since y>2, phi(y) is even so we get:

$a^{{\phi(x)}^{\frac{\phi(y)}{2}}}=-1$ mod(x). But (a,x)=1 so euler's theorem gives $a^{\phi(x)}=1$ mod(x). Also x>2 so 1 is not congruent to -1 mod(x). Therefore a contradiction has been established.