I need to prove the following:
For different primes, p and q, there exist, as a consequence of Bezout's Lemma, two natural numbers $a$ and $b$ with $ap - bq = 1$. Prove, if we encrypt $x = ap \bmod n$ (for $n = pq$), than the chiffre is equal to $x$.
How can I do this? I need to show that $D(x,(n,e)) = x^e \bmod n = (ap \bmod pq)^e = \ldots = x$
I have tried using Fermat's Little Theorem (from $x^p \equiv x \pmod p$), and also to show by contradiction: if $x = ap \bmod n$ is not a fixed point then this and that happens, but none of them seemed to help. How cand I solve this?
Thanks in advance :D
$x$ is the unique integer such that $0\leqslant x<n$, $x\equiv 0\pmod p$ and $x\equiv 1\pmod q$. Since $y=x^e\bmod n$ satisfies $y\equiv 0\pmod p$ and $y\equiv 1\pmod q$ as well, we must have $y=x$.