Since it means there is an inverse of mod . Let by the modular inverse.

Therefore,

Therefore, .

But divides since . Therfore, since . There is a factor of and therefore it is congruent to 0 mod p.

.2. If gcd(a, 35)=1, show that a^12 = 1(mod 35)

The exponent of this group is .

Therefore for .

It is sufficient to prove,3. If p and q are distinct primes, prove that

p^(q-1) + q^(p-1) = 1 (mod pq)

Can you finish now?