# Euler's Formula application for distinct odd primes with gcd 1

I am looking at the following question from my undergraduate Number Theory textbook:

Show that if p,q are different odd primes, and if gcd(p,q)=1, then a$$\Phi$$(pq)/2 $$\equiv$$ $$1$$ mod $$pq$$.

So far, the approach I have taken is trying to split up a$$\Phi$$(pq)/2 = (a$$\Phi$$(p)/2)$$\Phi$$(q) and apply Euler's theorem but I don't think I am really getting anywhere.

Any help would be greatly appreciated, thank you!

• Do you have $\gcd(a,pq) = 1$? – Calvin Lin Nov 13 at 3:54
• I added a proof to my answer. If anything is not clear please feel welcome to ask questions. Mastering the LCM & GCD Universal properties and their handy consequences as below will make elementary number theory much easier. – Bill Dubuque Nov 13 at 16:49

Note: If $$\gcd(a,pq) \neq 1$$, then clearly $$a^{ \phi (pq) / 2 } \neq 1 \pmod{pq}$$. So, I'm assuming that $$\gcd(a,pq) = 1$$.

Hint: $$\phi (pq) = (p-1)(q-1)$$, where both of the terms on the right are even, since they are odd primes.

Hence $$a^{\frac{(p-1)(q-1) } {2} } \equiv \left( a^{p-1} \right) ^ { \frac{q-1}{2} } \equiv 1 \pmod{p}$$.
Similarly for $$\pmod{q}$$, and hence for $$\pmod{pq}$$ (since they are distinct primes).

• @CalvinLin thank you! I think I thought about this problem for so long that I got lost in it, haha. The hint was very helpful to get me back on track. – Liv Nov 13 at 4:09
• @Liv You might find it helpful to view this in terms of basic $\rm lcm$ laws - which then leads the way to obvious generalizations that often prove handy, e.g. see my answer. – Bill Dubuque Nov 13 at 5:13

Hint $$\$$ It is the special case: \ \ \begin{align} &\ \ \ m,\ M,\ \ \, n,\,\ N,\ d\\ =\ &\phi(p),\,p,\,\phi(q),\,q,\ \ 2\end{align}\ \, in the $$\rm lcm$$-based generalization below

\!\begin{align}\text{The proof below shows that:} \ \ \ \ \color{#c00}{a^{\large m}}&\equiv \color{#c00}1\pmod{M}\\ a^{\large n} &\equiv 1\pmod {N}\end{align}\, \Rightarrow\ a^{\large\color{#0a0}{{\rm lcm}(m,n)}}\!\equiv 1\pmod{{\rm lcm}(M,N})

$${\rm so}\ \ d\mid m,n\,\Rightarrow\,m,n\mid mn/d\, \Rightarrow\ \color{#0a0}{{\rm lcm}(m,n)}\mid mn/d\ \Rightarrow\, \bbox[5px,border:1px solid #c00]{a^{\large mn/d}\ \equiv\ 1\ \ \pmod{{\rm lcm}(M,N})}$$

by applying $$\color{#90f}{\rm MOR}$$ = Modular Order Reduction  [or directly: $$\,a^{\large {\color{#0a0}{\ell}}}\equiv 1\,\Rightarrow\, a^{\large \ell\:\! k}\!\equiv (a^{\large\color{#0a0}{\ell}})^{\large k}\!\equiv 1^{\large k}\equiv 1$$]

Proof $$\$$ Let $$\,\ell={\rm lcm}(m,n).\,$$ Then $$\ m\mid\ell\$$ so $$\ \color{#c00}{a^{m} \equiv 1}\,\Rightarrow a^{\ell}\equiv 1\pmod{\!M},\,$$ again by $$\color{#90f}{\rm MOR}$$.

Same $$\!\bmod N,\,$$ so $$\, M,N\mid a^{\ell}-1\,\Rightarrow\,{\rm lcm}(M,N)\mid a^{\ell} -1\$$ [or we can use CCRT  vs. $$\,\rm lcm\!$$ ]

Hint: $$x\cong1\pmod p$$ and $$x\cong1\pmod q$$ implies $$x\cong1\pmod{pq}$$. For we have $$kp+1=x=lq+1\implies kp=lq\implies q\mid kp\implies q\mid k$$, by Euclid's lemma.

• i.e. apply CCRT = Constant case of CRT = Chinese Remainder Theorem (or. directly, we can use $\rm lcm$ as in the proof in my answer) – Bill Dubuque Nov 13 at 16:57