Exercise 3.14

Let p and q be distinct odd primes such that p − 1 divides q − 1 . If ( n , pq ) = 1 , show that n q − 1 ≡ 1 ( mod pq ) .

Answers

Proof. As n ∧ pq = 1 , n ∧ p = 1 , n ∧ q = 1 , so from Fermat’s Little Theorem

n q − 1 ≡ 1 ( mod q ) , n p − 1 ≡ 1 ( mod p ) .

p − 1 ∣ q − 1 , so there exists k ∈ ℤ such that q − 1 = k ( p − 1 ) . Thus

n q − 1 = ( n p − 1 ) k ≡ 1 ( mod p ) .

p ∣ n q − 1 − 1 , q ∣ n q − 1 − 1 , and p ∧ q = 1 , so pq ∣ n q − 1 − 1 :

n q − 1 ≡ 1 ( mod pq ) .

□

User profile picture
2022-07-19 00:00
Comments