promotion image of download ymail app
Promoted

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
  • atsuo
    Lv 6
    2 years ago
    Favorite 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 .

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.