1

If $p$ and $q$ are distinct odd primes, how could I approach showing that $x^{\varphi(pq)/\gcd(p-1,q-1)}\equiv 1\pmod {pq}$ for all $x\in (\mathbb Z/pq\mathbb Z)^\times$? I understand that $\varphi(pq)=(p-1)(q-1)$.

I've shown separately that $x^{1+k\varphi (pq)}\equiv x\pmod {pq}$ for all $k\geq 0$ and I know from Euler's theorem that $x^{\varphi (pq)}\equiv 1 \pmod {pq}$.

Can this be used to show that there is always an element of order $\varphi (pq)/\gcd(p-1,q-1)$ in $(\mathbb Z/pq\mathbb Z)^\times$? If not why?

GPhys
  • 1,539

1 Answers1

2

Let $d=\gcd(p-1,q-1)$. We show that $$x^{\varphi(pq)/d}\equiv 1\pmod{p}.$$ The same argument will show that the congruence holds modulo $q$, and therefore modulo $pq$.

Let $q-1=dw$. Then $$\frac{\varphi(pq)}{d}=(p-1)w.$$ So $p-1$ divides $\frac{\varphi(pq)}{d}$, and now the result follows from Fermat's Theorem.

We could have saved a bit of space by noting that $\frac{(p-1)(q-1)}{d}$ is the least common multiple of $p-1$ and $q-1$.

André Nicolas
  • 507,029
  • Does it help to show my last part, or is it unrelated? (That there must be an element of order $\mathrm{lcm}(p-1,q-1)$ in $(\mathbb{Z}/pq\mathbb{Z})^\times$) – GPhys Feb 12 '16 at 09:19
  • It is relevant, but the result does not immediately follow. We have shown that the order of any element divides the lcm, but not that there is an element of order the lcm. To do that we want to express the lcm as a product $st$ of numbers, where $s$ divides $p-1$, $t$ divides $q-1$ and $s$ and $t$ are relatively prime. The decomposition $(p-1)w$ that we used above is not into relatively prime numbers. – André Nicolas Feb 12 '16 at 09:58
  • After some (slightly nontrivial) thought, I found such a factoring by looking at $p-1=\prod _i p_i^{a_i}$ and $q-1=\prod _i p_i^{b_i}$ and making use of the fact that $\mathrm{lcm}(p-1,q-1)=\prod _i p_i^{\max {a_i,b_i}}$ so we can choose $s=\prod _{i\in{ i: a_i\geq b_i}} p_i^{a_i}$ and $t=\prod _{i\in{ i: b_i>a_i}} p_i^{b_i}$. $s$ and $t$ now meet the condition, but why must there now be something of order $st$? – GPhys Feb 12 '16 at 10:49
  • We know that $p$ and $q$ have primitive roots, that is, elements $a$ and $b$ of full order. And you probably know that if $a$ has order $s$ and $b$ has order $t$ and $s$ and $t$ are relatively prime then $ab$ has order $st$. – André Nicolas Feb 12 '16 at 12:02
  • Ah! I see the construction now. Thank you very much. – GPhys Feb 12 '16 at 12:38
  • Just to be certain I understand, the verbose statement is if $a$ has order $s$ mod $p$ and $b$ has order $t$ mod $q$ then $ab$ has order $st$ mod $pq$? – GPhys Feb 12 '16 at 13:19
  • About your comment just above: Right except it is missing a crucial necessary condition that $s$ and $t$ are relatively prime. – André Nicolas Feb 12 '16 at 13:55
  • Right, great. Thanks again. – GPhys Feb 12 '16 at 14:03