Track / Stage 5 / 287 of 400 #887 of 2000

Problem 887

AIME late

Number theory Difficulty 5.7 Prove it

Lemma 2.2. If $c$ and $d$ are integers and $c=d q+r$ where $c$ and $d$ are integers, then $(c, d)=(d, r)$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Proof. If an integer $e$ divides both $c$ and $d$ , then since $r=c-d q$ , Proposition 1.4 shows that $e \mid r$ . If $e \mid d$ and $e \mid r$ , then since $c=d q+r$ , from Proposition 1.4, we see that $e \mid c$ . Since the common divisors of $c$ and $d$ are the same as the common divisors of $d$ and $r$ , we see that $(c, d)=(d, r)$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.