## Trending News

# 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

### 1 Answer

Relevance

- 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)

Therefore

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 .

- Login to reply the answers

Still have questions? Get your answers by asking now.