Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.