# Proving that if $ed ≡ 1 \pmod{\frac12 φ(n)}$, then $y^{ed} ≡ y \pmod{ n}.$

This is actually the third step of the problem. It's preceded by these questions that I'm sure are supposed to lead me to solution.

$n = pq$, p and q distinct odd primes

First I'm supposed to show that $y^{\frac{1}{2}\phi(n)} \equiv 1 \pmod{ p}$ and that $y^{\frac{1}{2}\phi(n)} \equiv 1 \pmod{ q}$. $gcd(y, n) = 1$

Since $\phi(n) = (p-1)(q-1)$, I showed that $y^{\frac{1}{2}(p-1)(q-1)} \equiv [y^{\frac{1}{2}(q-1)}]$$^{(p-1)} \equiv 1 \pmod{ p} (by Fermat's Theorem) and did basically the same thing for the other equivalence relation. Does Fermat's theorem apply in this case? I'm hoping that it's safe to assume gcd(y^{\frac{1}{2}(q-1)}, p-1) =1 Then I was supposed to show that y^{\frac12\phi(n)} \equiv 1 \pmod{ n} from the previous steps, but I said that y^{\frac12\phi(n)} \equiv [y^{\frac12}] ^{\phi(n)} \equiv 1 \pmod{ n} by Euler's Theorem (again making a similar assumption) Then comes the question I posted in the title: Proving that if ed ≡ 1 \pmod{\frac12 φ(n)} , then y^{ed} ≡ y \pmod{ n}. I'm not really seeing the connection between these different statements which makes me think that I did the first ones wrong. I'm thrown off by the \frac12 because otherwise it's easy to see that y^{ed} ≡ y \pmod{ n}. \implies ed ≡ 1 \pmod{ φ(n)} . I'm not seeing how to prove that it still works with the \frac12. Any advice or anyone see where I did something wrong? Thanks! - ## 2 Answers Since y is prime to n (and p), so is y^{\frac12(q-1)} amd indeed little Fermat tells us that y^{\frac12\phi(n)}\equiv 1\pmod p. By symmetry, also y^{\frac12\phi(n)}\equiv 1\pmod q. Then by the Chinese Remainder Theorem, y^{\frac12\phi(n)}\equiv a\pmod n. So finally if ed=k\cdot\frac12\phi(n)+1 we find y^{ed}=\left(y^{\frac12\phi(n)}\right)^k\cdot y\equiv y\pmod n. - Let n = pq, p and q distinct odd primes Claim: y^{\frac{1}{2}\phi(n)} \equiv 1 \pmod{ p} and y^{\frac{1}{2}\phi(n)} \equiv 1 \pmod{ q}. As gcd(y, n) = 1 so gcd(p, n) = 1 and gcd(q, n) = 1, so by Fermat's theorem, y^{\phi(p)} \equiv 1\pmod{ p} and y^{\phi(q)} \equiv 1\pmod{ q} As p and q are distinct odd primes, so 2|(p-1) and 2|(q-1) or rather 2|\phi(p) and 2|\phi(q). y^{\frac{1}{2}(p-1)(q-1)} \equiv [y^{(p-1)}]$$^{\frac{1}{2}(q-1)}\equiv 1 \pmod{ p}$

Hence,$y^{\frac{1}{2}\phi(n)} \equiv 1 \pmod{ p}$ and $y^{\frac{1}{2}\phi(n)} \equiv 1 \pmod{ q}$.

From here can you see why we have $y^{\frac12\phi(n)} \equiv 1 \pmod{ n}$.

You can not safely assume things, you need a proof for anything you claim.

Claim: $ed ≡ 1 \pmod{\frac12 φ(n)}$, then $y^{ed} ≡ y \pmod{ n}.$

Now, if you have ${\frac12 φ(n)} | (ed-1)$ then $(ed-1) = k{\frac12 φ(n)}$for some $k \in N$

From here, can you see why $y^{ed} ≡ y \pmod{ n}.$

Hope this helps!!

-