8.27 Divisibility tutorial

1. What is the representation in base 2 of 109

   Solution:

   Using the division algorithm we have

   \(109=2\times 54+1\)

   \(54=2\times 27+0\)

   \(27=2\times 13+1\)

   \(13=2\times 6+1\)

   \(6=2\times 3+0\)

   \(3=2\times 1+1\)

   \(1=2\times 0+1\)

   Therefore the representation in base 2 of 109 is \((1101101)_2\)

2. Find the presentation in base 10 of \((4165)_7\)

   \(1468=7\times 209+5\)

   \(209=7\times 29+6\)

   \(29=7\times 4+1\)

   \(4=7\times 0 +4\)

   The presentation in base 10 of \((4165)_7\) is 1468

3. Prove that every perfect square leaves reminder 0 or 1 upon the division by 3

   \(n=3\times q+r(r=0,1,2)\)

   If \(n=3q\) then \(n^2=(3q)^2=3(3q^2)\) with \(3q^2\in\Z\) and by the uniqueness of the division algorithm \(n^2\) leaves remainder 0 upon division by 3.

   If \(n=3q+1\) then \(n^2=(3q+1)^2=3(3q^2+2q)+1\) with \(3q^2+2q\in\Z\) and by the uniqueness of the division algorithm \(n^2\) leaves remainder 1 upon division by 3.

   If \(n=3q+2\) then \(n^2=(3q+2)^2=3(3q^2+4q+1)+1\) with \(3q^2+4q+1\in\Z\) and by the uniqueness of the division algorithm \(n^2\) leaves remainder 1 upon division by 3.

‍

Remark

• \(a\mid0\) for every \(a\in\Z\) with \(a\neq 0\) since \(0=0(a)\)
• \(1\mid a\) for every \(a\in\Z\)​ since \(a=a(1)\)
• \(a\mid a\) for every \(a\in\Z\) with \(a\neq 0\) since \(a=1(a)\)​

‍

Theorem

1. \(a\mid b\Leftrightarrow a\mid-b\Leftrightarrow-a\mid b\Leftrightarrow-a\mid-b\)​

2. If \(a\mid b\) and \(b\mid c\) then \(a\mid c\)​

3. If \(a\mid b\) and \(b\mid a\) then \(a=b\) or \(a=-b\)​

4. If \(a\mid b\) then \(a\mid bc\)​

5. If \(a\mid b\) then \(ac\mid bc\)

6. If \(a\mid b\) and \(a\mid c\) then \(a\mid(\alpha b+\beta c)\) with \(\alpha,\beta\in\Z\)​

7. If \(a\mid(b\pm c)\) and \(a\mid b\) then \(a\mid c\)​

8. If \(a\mid b\) with \(b\neq 0\) then \(|a|\leq |b|\)​

Remark

• Every integer \(b\neq 0\) was only a finite number of divisors, that is, \(Div(b)\) is finite
• For any \(b\neq 0\) we have that \(-1,1,-b,b\) are always divisors of \(b\)​

‍

1. Find all \(a\in\Z\) with \(a\neq 1\) such that \(a-1\mid a^2+5\)​

   Solution

   Since \(a-1\mid a-1\), we have that \(a-1\mid(a-1)(a+1)=(a^2-1)\) and since \(a-1\mid a^2+5\) then

   \(a-1\mid(a^2+5)-(a^2-1)\)​

   \(a-1\mid6\)​

   that is, \(a-1\in Div(6)=\{-1,1,-2,2-3,3,-6-6\}\)​

   And thus \(a\in\{0,2,-1,3,-2,4,-5,7\}\)​

‍

Remark

• Note that a and b always have common divisors, for example 1
• As every non-zero integer has only a finite number of divisors, then a and b have only a finite number of common divisors

‍

Remark

• \(CDiv(a,b)=\{d\in\Z:d|a~and~d|b\}=Div(a)\cap Div(b)\)​
• \(CDiv(a,b)=\{d\in\N:d|a~and~d|b\}=Div_+(a)\cap Div_+(b)\)

‍

\(\begin{aligned}&Properties~of~the~gcd\\&\left(1\right)gcd\left(a,b\right)=gcd\left(b,a\right)\\&\left(c\right)gcd\left(a,b\right)=gcd\left(\left|a\right|,\left|b\right|\right)\\&\left(3\right)gcd\left(a,1\right)=1\\&\left(4\right)gcd\left(a,0\right)=\left|a\right|\\&\left(5\right)gcd\left(a,a\right)=\left|a\right|\end{aligned}\)

‍

1. Let \(a,b\in\Z\) with \(b\neq 0\). If \(b\mid a\) prove that \(gcd(a,b)=|b|\)​

   Proof

   Let \(d=gcd(a,b)\) then \(d\mid a\) and \(d\mid b\).

   Now, as \(b\mid a\) and \(b\mid b\) then \(b\mid d\).

   Hence \(d\mid b\) and \(b\mid d\).

   Therefore \(d=b\) or \(d=-b\)​

   Thus \(d=|b|\)​

   ‍

‍