Number Theory - How to Prove n^7 is Congruent to n Mod 63

[yeland404]

number theorm -- Euler theorem

Homework Statement

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

Homework Equations

none

The Attempt at a Solution

it is suffice to prove that n^7\equivn mod 7,n^7\equivn mod 9, i get
n^7\equivn mod 7 by Euler theorem , how to prove n^7\equivn mod 9

 

[Ninty64]

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?