# Number theorm - Euler theorem

1. Feb 14, 2012

### yeland404

number theorm -- Euler theorem

1. The problem statement, all variables and given/known data

let be an integer that not divisible by 3. Prove that n^7$\equiv$n mod 63

2. Relevant equations

none

3. The attempt at a solution
it is suffice to prove that n^7$\equiv$n mod 7,n^7$\equiv$n mod 9, i get
n^7$\equiv$n mod 7 by Euler theorem , how to prove n^7$\equiv$n mod 9

2. Feb 14, 2012

### Ninty64

Re: number theorm -- Euler theorem

Remember that Euler's totient function, $\varphi (n)$ is equal to the number of positive integers less than or equal to n that are coprime to n. What is $\varphi (9)$ and what does that imply by Euler's Theorem?