Suppose 1 ≤ k ≤ n − 1 and gcd(k, n) = 1. Prove that gcd(n − k, n) = 1.?
I have no idea where to start. Any help would be appreciated
- atsuoLv 61 year agoFavorite Answer
GCD(k,n) = 1 means that k and n have no common divider . Similarly ,
GCD(n-k,n) = 1 means that n-k and n have no common divider .
Assume that n-k and n have a common divider c(≠1) . So
n-k = cp (p is a positive integer)
n = cq (q is a positive integer and p < q)
n - (n-k) = c(q-p) ... q-p becomes a positive integer
k = c(q-p)
So c is a divider of k .
But n = cq , so c is a divider of n .
So c becomes a common divider of k and n . This is a contradiction .
Therefore , n-k and n have no common divider . That is , GCD(n-k,n) = 1 .