6
$\begingroup$

From Ireland's Number theory book, Ch.3 ex. 6.

Let and integer $n>0$ be given. A set of integers $a_{1},a_{2}, \cdots ,a_{\phi(n)}$ is called a reduced residue system modulo $n$ if they are pairwise incongruent mod n and $(a_{i},n)=1$ for all $i$. If additionally $(a,n)=1$, prove that $aa_{1},aa_{2}, \cdots ,aa_{\phi(n)}$ is again a reduced residue system modulo n.

I can solve this problem, however, it is not clear to me how this result helps in the following (ex7)

Use ex.6 to give another proof of Euler's therorem, $a^{\phi(n)}\equiv 1 \pmod{n}$ for $(a,n)=1$

$\endgroup$
5
$\begingroup$

There are exactly $\phi(n)$ elements of $\mathbb{Z}/n\mathbb{Z}$ that lift up to integers coprime with $n$, so any reduced residue system corresponds to exactly the same set of representatives in the ring of integers. This means that the product $a_1\cdots a_{\phi(n)}$ is the same as $b_1\cdots b_{\phi(n)}$ modulo $n$ when $a_i$ and $b_i$ are two such systems. Take $b_i=aa_i$ and then divide out both sides of the equality by $a_1\cdots a_{\phi(n)}$ to obtain Euler's.

$\endgroup$
  • $\begingroup$ @Edison: It is worth noting that the product $a_1 \cdots a_{\phi(n)}$ is nonzero (if it were zero, the final division step would be invalid). $\endgroup$ – Srivatsan Feb 1 '12 at 5:48
4
$\begingroup$

If $a_1,\ldots,a_{\phi(n)}$ is a reduced residue system, then so is $aa_1,aa_2,\ldots,aa_{\phi(n)}$. Therefore, $$a_1a_2\cdots a_{\phi(n)} \equiv (aa_1)(aa_2)\cdots(aa_{\phi(n)}) \equiv a^{\phi(n)}(a_1\cdots a_{\phi(n)})\pmod{n}.$$

$\endgroup$
3
$\begingroup$

HINT: If $a_{1}, a_{2}, \cdots , a_{\phi(n)}$ and $b_{1}, b_{2}, \cdots , b_{\phi(n)}$ are two reduced bases, what can you say about the products

$\displaystyle \prod_{i=1}^{\phi(n)} a_i $

and

$\displaystyle \prod_{i=1}^{\phi(n)} b_i? $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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