17 - Divisibility

Divisibility and Common Divisors

The division algorithm

!Screenshot 2023-10-18 at 12.43.02 AM.png

GCD

!Screenshot 2023-10-18 at 12.44.08 AM.png

In class practice

Def: A common divisor of two integers $a,b$ is an integer $c$ such that $c\mid a$ and $c\mid b$

GCD switching theorem

GCD(39, 57) = ?
57 = 1(39) + 18
39 = 2(18) + 3
18 = 6(3) + 0
Once you get to zero, the last remainder is the GCD

So the GCD is 3

17.1g
n = -256, d = 25

-256 = -11(25) + 19

GCD(1855, 2345)
2345 = 1(1855) + 490
1855 = 3(490) + 385
490 = 1(385) + 105
385 = 3(105) + 70
105 = 1(70) + 35
70 = 2(35) + 0
GCD = 35

Theorem 17.13. Fix $d>0$. We work by induction to prove that
$P(n):$ there are integers $q_n,r_n$ such that $n=q_{n}d+r_n$ and $0\le r_n<d$ is true for each $n\ge 0$.

Sketch. Base case: $P(0)$ is true because $0=0(d)+0$

Inductive step.
Let $k\in \mathbb{N}\cup \{0\}$
Assume that $P(k)$ is true

HW 17

Ben Finch

E 17.1
(a) q=3, r=2
(b) q=-3, r=3
(c) q=-4, r=3
(d) q=4, r=3
(e) q=10, r=6.
(f) q=-10, r=6
(g) q=-11, r=19
(h) q=11, r=19

E 17.2
a)
Proof.
Let $n\in \mathbb{Z}$.
Fix $d=2$.
By the division algorithm, $n=2q+r$ for some $q,r\in \mathbb{Z}$. Thus $n=2q+0$(which would mean $n$ is an even number) or $n=2q+1$ (which would mean $n$ is an odd number). Hence all integers are even or odd. $◻$

b)
Proof.
Let $n\in \mathbb{Z}$.
Assume by way of contradiction that $n$ is both an odd and even number. Then $n=2k+1$ and $n=2k$ for some $k\in \mathbb{Z}$. We find

Herein lies our contradiction. Thus $n$ cannot be both and even and an odd number $◻$.

E 17.3
Divisors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Divisors of 42: 1, 2, 3, 6, 7, 14, 21, 42

Common divisors: 1, 2, 3, 6

GCD: 6

E 17.4
a) GCD(60, 42)
60 = 1(42) + 18
42 = 2(18) + 6
18 = 6(3) + 0
GCD = 6

b) GCD(667,851)
851 = 1(667) + 184
667 = 3(184) + 115
184 = 1(115) + 69
115 = 1(69) + 46
69 = 1(46) + 23
46 = 2(23) + 0
GCD = 23

c) GCD(1855, 2345)
2345 = 1(1855) + 490
1855 = 3(490) + 385
490 = 1(385) + 105
385 = 3(105) + 70
105 = 1(70) + 35
70 = 2(35) + 0
GCD = 35

d) GCD(589, 437)
589 = 1(437) + 152
437 = 2(152) + 128
152 = 1(128) + 24
128 = 5(24) + 8
24 = 3(8) + 0
GCD = 8

E 17.5
Proof.
Let

Base Cases:
n = 1, GCD($F_2,F_1$) = GCD(1, 1) = 1
n = 2, GCD($F_3,F_2$) = GCD(2, 1) = 1
n =3, GCD($F_4,F_3$) = GCD(3, 2) = 1

Inductive Step:
Assume that for $k\ge 3$, $k\in \mathbb{N}$ that GCD($F_{k+1},F_k$) = 1

We aim to show that GCD($F_{k+2},F_{k+1}$) = 1

By the definition of Fibonacci numbers: $F_{k+2}=F_{k+1}+F_k$

By the GCD-Switching Theorem:
GCD(a, b) = GCD(b, c) if $a=xb+c$. Fix $x=1$. We have $a=b+c$. now sub in $a=F_{k+2}$, $b=F_{k+1}$, $c=F_k$. By the inductive hypothesis, GCD($F_{k+1},F_k$) = 1 and thus GCD($F_{k+2},F_{k+1}$) = 1.

Hence by mathematical induction $P(n)$ is true for all Fibonacci numbers. $◻$

E 17.6
Proof.
Let $n\in \mathbb{Z}$. Apply the Euclidean algorithm to get the GCD($4n+2,2n+1$):

Thus the GCD is 1. $◻$

E 17.7
Proof.
Let $n\in \mathbb{Z}$. Apply the Euclidian algorithm to get GCD($6n+2,12n+6$):

Thus the GCD is 2. $◻$

E 17.8

(a) Proof. Suppose $n<0$ and $d>0$. Applying the division theorem to $-n$ and $d$, we can write $-n=q^{\prime }d+r^{\prime }$, where $q^{\prime }$ and $r^{\prime }$ are integers and $0\le r^{\prime }<d$. Thus, we can write $n=(-q^{\prime })d-r^{\prime }$.

If $r^{\prime }=0$, then $n=(-q^{\prime })d$ and we have our representation. If $r^{\prime }\ne 0$, then we can adjust as follows: $n=(-q^{\prime }-1)d+(d-r^{\prime })$. Since $r^{\prime }<d$, $d-r^{\prime }$ is in the interval $[0,d)$, thereby providing the desired representation for $n$. Thus the theorem is proven for $n<0$ and $d>0$. $◻$

(b) Suppose $d<0$. Applying the already proven case of the theorem to $n$ and $-d$ gives us $n=q^{″}(-d)+r^{″}$, where $q^{″}$ and $r^{″}$ are integers and $0\le r^{″}<|-d|$. If we let $q=-q^{″}$, then we can write this as $n=qd+r^{″}$, with $0\le r^{″}<|d|$, as required.

Thus, we have proved the Division Algorithm for all integers $n$ and nonzero integers $d$. $◻$