Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
@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). –  Srivatsan Feb 1 '12 at 5:48

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}.$$

share|improve this answer

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? $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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