6. Integers, divisibility and rational constructions

Learning goals and definitions

Prove divisibility results without numerical guesswork, construct rational numbers from integer pairs, and separate rational algebra from completeness of the reals. For integers $a,b$, $a\mid b$ means $b=ak$ for some integer $k$. A prime is an integer $p\ge2$ whose positive divisors are only $1,p$. The greatest common divisor $\gcd(a,b)$ of not-both-zero integers is their greatest positive common divisor.

Theorem: integer division and Bezout's identity

For integers $a$ and $b>0$ there are unique integers $q,r$ with $a=bq+r$ and $0\le r<b$. For not-both-zero integers $a,b$, there exist integers $s,t$ such that $\gcd(a,b)=sa+tb$.

Proof of division. Among nonnegative integers of the form $a-bq$, choose the least $r$; such integers exist by taking $q$ sufficiently negative. If $r\ge b$, then $r-b$ is a smaller nonnegative candidate, a contradiction. If two divisions exist, their remainders differ by a multiple of $b$ whose magnitude is less than $b$, so the difference is zero and then the quotients agree.

Proof of Bezout. Positive integer combinations $sa+tb$ exist because one of $a,b$ is nonzero and its sign can be chosen. Choose the least such positive combination $d$. Divide $a$ by $d$; its remainder is also an integer combination, so minimality forces remainder zero. Similarly $d\mid b$. Any common divisor of $a,b$ divides every combination and hence $d$. Thus $d$ is the greatest positive common divisor and has the required representation.

Consequence: Euclid's lemma. If a prime $p$ divides $ab$ and does not divide $a$, then $\gcd(p,a)=1$. Write $sp+ta=1$ and multiply by $b$. Each term on the left is divisible by $p$, so $p\mid b$. This is the missing ingredient for proving uniqueness of prime factorization, beyond the existence induction.

Rational numbers as equivalence classes

Take integer pairs $(a,b)$ with $b\ne0$ and define $(a,b)\sim(c,d)$ when $ad=bc$. Reflexivity and symmetry are immediate. For transitivity, $ad=bc$ and $cf=de$ imply $adf=bcf=bde$; cancelling nonzero $d$ gives $af=be$. Thus the relation is an equivalence relation. Its classes are the rational numbers $a/b$.

Define addition by $a/b+c/d=(ad+bc)/(bd)$ and multiplication by $(a/b)(c/d)=ac/(bd)$. These rules must be independent of representatives. For example, if $ab'=a'b$ and $cd'=c'd$, then $acb'd'=(ab')(cd')=(a'b)(c'd)=a'c'bd$, verifying product independence. The addition check follows by expanding $(ad+bc)b'd'$ and substituting the same two identities. Nonzero denominators are essential to the construction.

Worked examples

The Euclidean algorithm. $252=1(198)+54$, $198=3(54)+36$, $54=1(36)+18$, $36=2(18)$. Back-substitution gives $18=4(252)-5(198)$, so the gcd is $18$. The division steps preserve the common-divisor set because a divisor of two numbers divides their remainder and conversely.

An irrationality proof. If $\sqrt2=a/b$ in lowest terms with positive integers $a,b$, then $a^2=2b^2$. An even square has an even base, so $a=2c$. Substitution gives $b^2=2c^2$, hence $b$ is even too. Both share factor two, contradicting lowest terms. This proof excludes rational equality; it does not construct the real square root or prove completeness of $\mathbb R$.

Graded practice

1. Foundation. Divide $-17$ by $5$ with a remainder in the required range.
2. Core. Find $\gcd(35,22)$ and express it as an integer combination.
3. Core. Prove $\sqrt3$ is irrational, using Euclid's lemma.
4. Proof. If $\gcd(a,m)=1$ and $a x\equiv a y\pmod m$, prove $x\equiv y\pmod m$. Give a counterexample without coprimality.

Full solutions

1. $-17=5(-4)+3$, with $0\le3<5$. Using quotient $-3$ would produce negative remainder and violate the chosen convention.
2. $35=22+13$, $22=13+9$, $13=9+4$, $9=2(4)+1$. Back-substitution gives $1=8(22)-5(35)$, so the gcd is one.
3. Suppose $\sqrt3=a/b$ in lowest terms with $b>0$. Then $a^2=3b^2$, so Euclid's lemma gives $3\mid a$. Write $a=3c$ to obtain $b^2=3c^2$, so $3\mid b$ too, contradicting coprimality.
4. Bezout gives $sa+tm=1$. Multiplying by $x-y$, both terms on the left are divisible by $m$ because $m\mid a(x-y)$. Thus $m\mid x-y$. Without coprimality, $2\cdot0\equiv2\cdot2\pmod4$ but $0\not\equiv2\pmod4$.

Summary and term definitions

Divisibility is an integer multiple relation; a gcd is normalized positive. Coprime means gcd one; Bezout coefficients express that gcd as a linear combination. A rational number is a class of equivalent fractions, not a unique numerator–denominator pair. Each extension of a number system requires well-defined operations, while real completeness is an additional property beyond rational arithmetic.