◀ ▲ ▶Branches / Number-theory / Proof

Proof

(related to Lemma: Division with Quotient and Remainder)

• Let $a,b\in\mathbb Z$ be integers with $a > 0.$
• We first show that there is at least one pair of integers $q,r$ fulfilling $$b=qa + r,\quad 0\le r < a.\quad\quad ( * )$$
  • Among the integers $b-ua$ there are negative and positive ones for sufficiently large negative or positive integer $u.$
  • The set $S:=\{b-ua\mid u\in\mathbb Z\wedge b-ua\ge 0\}$ of non-negetive integers $b-ua$ is not empty. Since this is a non-empty subset of natural numbers $S\subset \mathbb N$ and the ordered natural numbers $(N,\le)$ are well-ordered, there exists a minimum $\min(S)$ for some $u_0\in\mathbb Z.$
  • We set $q:=u_0$ and $r:=b-qa.$ Then we have $b-qa\ge 0$ and $r-a=b-(q-1)a < 0.$
  • This shows that the constructed $q,r$ solve $( * ).$
• We now show that there is at most one pair of integers $q,r$ fulfilling $( * ).$
  • If we have found some $q,r$ fulfilling $( * ),$ then if $u < q$ then $u\le q-1$ and $b-ua\ge b-(q-1)a=r+a\ge a.$
  • If we have found some $q,r$ fulfilling $( * ),$ then if $u > q$ then $u\ge q+1$ and $b-ua\le b-(q+1)a=r-a < 0.$
  • From this it follows that $0\le b-ua < a$ can only be fulfilled if $u=q.$
    ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Kramer Jürg, von Pippich, Anna-Maria: "Von den natürlichen Zahlen zu den Quaternionen", Springer-Spektrum, 2013