# Calculate using Chinese remainder theorem

Let $p,q\in \mathbb{N}$ primes and $a,b\in \mathbb{Z}$ such that $a^e \equiv a \mod p$ and $b^e \equiv b \mod p$. By Chinese remainder theorem we know that existis a unique $x\in \mathbb{Z}$ (mod pq) which satisfies $$x \equiv a \mod p \qquad x \equiv b \mod q$$ Calculate $x^e \mod pq$.

Sol. $$x^e \equiv a^e \equiv a \equiv x\mod p \qquad x^e \equiv b^e \equiv b \equiv x \mod q$$ $$p \mid x^e - x\qquad q \mid x^e - x$$ Using $p,q$ are primes, $pq \mid x^e-x$ so $x^e \equiv x \mod pq$.

• Are we supposed to calculate its residue class mod $pq$? – G Tony Jacobs May 19 '17 at 17:14
• @GTonyJacobs Sorry, my fault. – Rafael Gonzalez Lopez May 19 '17 at 17:19

## 1 Answer

Since we have $x\equiv a\pmod{p}$, then we can raise both sides to the power $e$, and say $x^e\equiv a^e\equiv a\pmod{p}$. We can do the same thing with our given fact modulo $q$.

Does that give you enough of a push in the right direction?

• I knew that, but let me think. Thank you. – Rafael Gonzalez Lopez May 19 '17 at 17:24
• Sorry I delete some comments. It was wrong ideas. I can't do it :< @GTonyJacobs – Rafael Gonzalez Lopez May 20 '17 at 11:46
• I've got it. Ty – Rafael Gonzalez Lopez May 20 '17 at 12:54