- Thread starter
- Banned
- #1
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]$$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]
[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]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?