1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Congruence and GCD Proof

  1. Feb 21, 2015 #1
    1. The problem statement, all variables and given/known data
    If a≡b(mod n) and d=gcd(a.n), prove that d=gcd(b,n).

    2. Relevant equations
    If a≡b(mod n) → n|(a-b) → a-b =nk, for some k∈ℤ → a=nk+b
    If d=gcd(a.n) → d=ax+ny
    gcd(b,n)=d ↔ d|b and d|n, and if c|b and c|n, then c ≤ a.

    3. The attempt at a solution
    Since a=nk+b and d=ax+ny, then
    d=bx+nw, where w=kx+y and w∈ℤ.

    I have gotten this far. Originally I thought this was enough to prove d was the gcd of b and n. But now I see that I need to show d|b, d|n, and that if there is a c such that c|b and c|n, then c ≤ d.

  2. jcsd
  3. Feb 21, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper

    It's pretty clear that if d|n and d|a then d|b, right? Show that. Now if there is a smaller c that also divides b and n, then it also must divide a and n, right? Show that. Put the two together.
    Last edited: Feb 21, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted