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

Question

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!

Answer 1

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$.

Answer 2

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!!