- Thread starter
- Banned
- #1

- Thread starter Poirot
- Start date

- Thread starter
- Banned
- #1

- Jan 26, 2012

- 644

Explanations and justifications below:

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

Last edited:

- Thread starter
- Banned
- #3

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?

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]

- Jan 26, 2012

- 644

[JUSTIFY]Yes, that is a good point. What is missing is that the step has to follow forYour 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?

- Thread starter
- Banned
- #5

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.