# Thread: prime number

1. ## prime number

let p and q be distinct odd prime numbers with p-1 divides q-1. If a is with in integers with (a,pq)=1 prove that a^q-1=1mod pq

2. Originally Posted by rmpatel5
let p and q be distinct odd prime numbers with p-1 divides q-1. If a is with in integers with (a,pq)=1 prove that a^q-1=1mod pq
let $q-1=d(p-1).$ since $\gcd(a,q)=1,$ we have $a^{q-1} \equiv 1 \mod q.$ also since $\gcd(a,p)=1,$ we have: $a^{p-1} \equiv 1 \mod p,$ which gives us: $a^{q-1}=(a^{p-1})^d \equiv 1 \mod p.$

so we showed that both $p$ and $q$ divide $a^{q-1}-1,$ and thus $pq$ must also divide $a^{q-1} - 1. \ \ \ \square$