The remainder of $a÷b$ is $c$, both $a$ and $b$ are positive integers.

How to prove:

  1. $gcd(c,b)=1 \iff gcd(a,b)=1$

  2. $gcd(a,b)=1 \iff gcd(c,b)=1$

  • 2
    $\begingroup$ The two statements are the same, and is a direct consequence of $\gcd(a,b) = \gcd(a-b,b)$. $\endgroup$
    – player3236
    Jan 7, 2021 at 6:33

1 Answer 1


let $a = bq + c$ for some integer $q$.

Then if say $gcd(a,b) = 1$, and $gcd(b,c) = m$,

then, from $a = bq +c$ ;

we will get $m|a$ but $m$ also divides $b$ $\implies$ $m$ is a common divisor of $a$ and $b$ , And the only common divisor of $a$ and $b$ is 1.


Not the answer you're looking for? Browse other questions tagged .