The Division Algorithm

Dividend ⎣ Divisor
 *        Quotient
  *
   Remainder

Dividend = divisor * quotient + remainder

Divisibility

An important case of division occurs when the remainder is 0, that is when the divisor is a factor of the dividend.

Let $a$ and $b$ be integers with $b ≠ 0$ . We say that $b$ divides $a$ (or that $b$ is a divi­sor of $a$, or that $b$ is a factor of $a$) if $a =bc$ for some integer $c$.

In symbols, " $b$ divides $a$" is written $b|a$ and " $b$ does not divide $a$" is written $b∤a$.

[ A \text{ is divisible by } B \text{ if and only if } \exists k \in \mathbb{Z} \text{ such that } A = B \cdot k ]

[ A ∣ B ⟺ \exists k \in \mathbb{Z} : A = B \cdot k ]

This formula states that "A is divisible by B" if there exists an integer "k" such that when you multiply B by k, you get A without any remainder.

Divisibility Rules

To determine whether a number is divisible by another, we often use divisibility rules. These rules are simple guidelines that tell us when one number divides another without leaving a remainder. Common rules include divisibility by 2, 3, 5, and 10.

Divisibility by 2

• A number is divisible by 2 if it ends in an even digit (0, 2, 4, 6, or 8).

Divisibility by 3

Divisibility by 3 is determined by the sum of a number's digits. These have to add to 3, 6, 9, or other number divisible by 3.

Divisibility by 5

Divisibility by 5 is related to a number's last digit. If a number ends in 0 or 5, it's divisible by 5.

Divisibility by 10

Divisibility by 10 is the simplest rule of all. If a number ends in 0, it's divisible by 10.

Practical Applications

Divisibility plays a crucial role in various areas of mathematics and daily life, such as simplifying fractions, prime factorization, and determining common multiples.

Prime Factorization

Least Common Multiple

Greatest Common Factor

Addition & Subtraction of Fractions

Multiplication & Division of Fractions

Exercises

Solve the following divisions of the form:

Dividend ⎣ Divisor
 *        Quotient
  *
   Remainder

Dividend = divisor * quotient + remainder

17 ⎣ 4
     4
16
 1 

17 = 4*4 + 1

0 ⎣ 19
     0
0
 0 

0 = 19*0 + 0

-17 ⎣ 4
      -4
-16
  -1

-17 = 4 * 4̚ + 1̚

-51 ⎣ 6
      -8
-48
  -3

-51 = 6 * 8̚ + 3̚

302 ⎣ 19
-     10 + 5
190
= 112
 - 95
 = 17

302 = 19 * 15 + 17

2000 ⎣ 17
-      100 + 10 + 7
1700
= 300 
- 170
 = 130
  - 70
  - 49
  = 11

2000 = 17 * 117 + 11

X: ac = bc·q + rc

Let $a$ be any integer and let $b$ and $c$ be positive integers. Suppose that

a = bq + r 

and 0≤r<b

If $ac$ is divided by $bc$, show that the quotient is $q$ and the reminder is $rc$

To prove that when $ac$ is divided by $bc$, the quotient is $q$ and the remainder is $rc$, you can use the properties of integer division.

Let's start with the expression for $a$ divided by $b$:

$a = bq + r$

Now, we want to consider $ac$ divided by $bc$:

$ac = bcq + rc$

To show that $q$ is the quotient and $rc$ is the reminder when $ac$ is divided by $bc$, we need to show that 0≤rc<bc

\frac{ac}{bc} = \frac{bcq + rc}{bc} = q + \frac{rc}{bc}

ac = bc·q + rc

Now, we have $q$ as the whole number part of the quotient. To show that $rc$ is the remainder, we need to show that $\frac{rc}{bc}$ is a proper fraction, meaning its numerator is less than its denominator.

Since 0≤r<b and $c$ is a positive integer, we have:

0≤rc<bc

Now, let's divide both sides by $bc$ (which is positive) to ensure $\frac{rc}{bc}$ is a proper fraction:

0≤ $\frac{rc}{bc}$ < 1

This shows that $\frac{rc}{bc}$ is indeed a proper fraction, which means $q$ is the quotient, and $rc$ is the remainder when $ac$ is divided by $bc$.

So, we have demonstrated that when $a$ is divided by $b$ with quotient $q$ and reminder $r$, and $ac$ is divided by $bc$, the quotient is also $q$, and the reminder is $rc$, satisfying the conditions of integer division.

X: 3k

Prove that the square of any integer $a$ is either of the form $3k$ or of the form $3k + 1$ for some integer $k$. [Hint: By the Division Algorithm, $a$ must be of the form $3q$ or $3q + 1$ or $3q + 2$.]

To prove that the square of any integer $a$ is either of the form $3k$ or $3k+1$ for some integer $k$, you can use the hint provided and apply the Division Algorithm.

The Division Algorithm states that for any integer $a$ and positive integer $b$, there exist unique integers $q$ and $r$ such that:
$a = bq + r$
where 0≤r<b

Now, consider the three possible cases for $a$ when divided by $3$, as mentioned in the hint:

1. $a=3q$: In this case, $a$ is a multiple of $3$, and its square is $a^2=(3q)^2=9q^2$. Since $9q^2$ is a multiple of $3$, it is of the form $3k$ for some integer $k$.

2. $a=3q+1$: In this case, $a$ leaves a remainder of $1$ when divided by $3$, and its square is $a^2=(3q+1)^2=9q^2+6q+1$. Notice that $9q^2+6q$ is a multiple of $3$ (it's $3(3q^2+2q)$), so when you add $1$ to a multiple of $3$, you still get a number of the form $3k$ for some integer $k$.

3. $a=3q+2$: In this case, $a$ leaves a remainder of $2$ when divided by $3$, and its square is $a^2=(3q+2)^2=9q^2+12q+4$. Similar to the second case, $9q^2+12q$ is a multiple of $3$ (it's $3(3q^2+4q)$), so when you add $4$ to a multiple of $3$, you still get a number of the form $3k$ for some integer $k$.

In all three cases, the square of $a$ can be expressed in the form $3k$ or $3k+1$ for some integer $k$, as required. Therefore, the statement is proven.

X: 4k + 1

Use the Division Algorithm to prove that every odd integer is either of the form $4k + 1$ or of the form $4k + 3$ for some integer $k$.

To prove that every odd integer is either of the form $(4k + 1)$ or $(4k + 3)$ for some integer $(k)$, we can use the Division Algorithm.

The Division Algorithm states that for any integer $(a)$ and positive integer $(b)$, there exist unique integers $(q)$ and $(r)$ such that:
$[a = bq + r]$
where $(0 \leq r < b)$.

Now, let's consider the division of an odd integer $(a)$ by $(4)$, where $(a)$ is odd.

Case 1: $(a = 4q)$ In this case, $(a)$ is a multiple of $(4)$, and it can be written as $(a = 4q)$. But $(4q)$ is even, not odd. This case doesn't apply to odd integers.

Case 2: $(a = 4q + 1)$ In this case, $(a)$ leaves a remainder of $(1)$ when divided by $(4)$, and it can be written as $(a = 4q + 1)$, where $(q)$ is an integer. This is of the form $(4k + 1)$, where $(k = q)$.

Case 3: $(a = 4q + 2)$ In this case, $(a)$ leaves a remainder of $(2)$ when divided by $(4)$, and it can be written as $(a = 4q + 2)$. However, $(4q + 2)$ is even, not odd. This case doesn't apply to odd integers.

Case 4: $(a = 4q + 3)$ In this case, $(a)$ leaves a remainder of $(3)$ when divided by $(4)$, and it can be written as $(a = 4q + 3)$, where $(q)$ is an integer. This is of the form $(4k + 3)$, where $(k = q)$.

In summary, for any odd integer $(a)$, it can be expressed as either $(4k + 1)$ or $(4k + 3)$ for some integer $(k)$. This concludes the proof that every odd integer is either of the form $(4k + 1)$ or $(4k + 3)$.

X: Cube: 9k

Prove that the cube of any integer a has to be exactly one of these forms: (9k) or (9k +1) or (9k + 8) for some integer (k).

To prove that the cube of any integer $(a)$ is either of the form $(9k)$, $(9k + 1)$, or $(9k + 8)$ for some integer $(k)$, you can use the Division Algorithm.

The Division Algorithm states that for any integer $(a)$ and positive integer $(b)$, there exist unique integers $(q)$ and $(r)$ such that:
$[a = bq + r]$
where $(0 \leq r < b)$.

Now, let's consider the cube of an integer $(a)$.

$[a^3 = a \cdot a \cdot a]$

We can express this as:

$[a^3 = a^2 \cdot a]$

So, we need to consider the forms of $(a^2)$ and $(a)$ to determine the form of $(a^3)$.

First, consider $(a^2)$. By applying the Division Algorithm to $(a)$ divided by $(3)$, we have three possible cases:

1. $(a = 3q)$: In this case, $(a)$ is a multiple of $(3)$, and $(a^2 = (3q)^2 = 9q^2)$. This is of the form $(3k)$ for some integer $(k)$ (where $(k = 3q^2)$ ).

2. $(a = 3q + 1)$: In this case, $(a)$ leaves a remainder of $(1)$ when divided by $(3)$, and $(a^2 = (3q + 1)^2 = 9q^2 + 6q + 1)$. Notice that $(9q^2 + 6q)$ is a multiple of $(3)$ (it's $(3(3q^2 + 2q))$ ), so when you add $(1)$ to a multiple of $(3)$, you get a number of the form $(3k + 1)$ for some integer $(k)$ (where $(k = 3q^2 + 2q)$ ).

3. $(a = 3q + 2)$: In this case, $(a)$ leaves a remainder of $(2)$ when divided by $(3)$, and $(a^2 = (3q + 2)^2 = 9q^2 + 12q + 4)$. Similar to case 2, $(9q^2 + 12q)$ is a multiple of $(3)$ (it's $(3(3q^2 + 4q))$ ), so when you add $(4)$ to a multiple of $(3)$, you get a number of the form $(3k + 1)$ for some integer $(k)$ (where $(k = 3q^2 + 4q\ + 1)$ ).

Now, we have shown that $(a^2)$ can be expressed as either $(9k)$, $(9k + 1)$, or $(9k + 1)$ for some integer $(k)$ based on the three possible cases for $(a)$.

To determine the form of $(a^3)$, let's multiply $(a^2)$ by $(a)$:

$[a^3 = a^2 \cdot a]$

We've already established the forms of $(a^2)$, and when you multiply them by $(a)$, the resulting $(a^3)$ will also be of the same form.

We've established the forms of $(a^2)$:

1. If $(a = 3q)$, then $(a^2)$ is of the form $(3k)$ for some integer $(k)$ when $(a)$ is a multiple of $(3)$ (i.e., $(a = 3q)$ ), where $(k = 3q^2)$ .
2. If $(a = 3q + 1)$, then $(a^2)$ is of the form $(3k + 1)$ for some integer $(k)$ when $(a)$ leaves a remainder of $(1)$ when divided by $(3)$ (i.e., $(a = 3q + 1)$ ), where $(k = 3q^2 + 2q)$ .
3. If $(a = 3q + 2)$, then $(a^2)$ is also of the form $(3k + 1)$ for some integer $(k)$ when $(a)$ leaves a remainder of $(2)$ when divided by $(3)$ (i.e., $(a = 3q + 2)$ ), where $(k = 3q^2 + 4q + 1)$ .

Now, we want to determine the form of $(a^3)$, which is found by multiplying $(a^2)$ by $(a)$:

$[a^3 = a^2 \cdot a]$

We will analyze the three cases separately:

1. 1. $(a = 3q)$: In this case, $(a)$ is a multiple of $(3)$, and $(a^2)$ is of the form $(3k)$ for some integer $(k)$ (where $(k = 3q^2)$, with $k$ an integer ).

$[a^3 = (3k) \cdot (3q) = 9kq = 9k']$

Since both $(k)$ and $(q)$ are integers, $(9kq)$ is of the form $(9k')$, where $(k')$ is an integer. So, $(a^3)$ is of the form $(9k')$.

2. If $(a = 3q + 1)$, and if $(a^2 = 3k + 1)$, then when we multiply it by $(a)$, we get:

[ a^3 = (3k + 1) \cdot (3q + 1) = 9kq + 3k + 3q + 1 = 9(3q^2 + 2q)q + 3(3q^2 + 2q) + 3q + 1 = 27q^3 + 18q^2 + 9q^2 + 6q + 3q + 1 =  27q^3 + 18q^2 + 9q^2 + 9q + 1  = 9(3q^3 + 2q^2 + q^2 + q) + 1 = 9k' + 1 ]

[a^3 = 9k' + 1 ]

Again, since both $(k)$ and $(q)$ are integers, $(a^3)$ is of the form $(9k' + 1)$. Therefore, $(9ka + a)$, where $(k')$ is an integer. So, $(a^3)$ is of the form $(9k' + 1)$.

3. If $(a = 3q + 2)$, and $(a^2 = 3k + 1)$, then when we multiply it by $(a)$, we get:

[ a^3 = (3k + 1) \cdot (3q + 2) 
= 9kq + 6k + 3q + 2 
= 9(3q^2 + 4q + 1)q + 6(3q^2 + 4q + 1) + 3q + 2 
= 27q^3 + 36q^2 + 9q + 18q^2 + 24q + 6 + 3q + 2 
= 27q^3 + 54q^2 + 36q + 8 
= 9q^2(3q+6) + 4(9q+2)
= 9 (q^2(3q+6) + 4q) + 8)
= 9 k' + 8)
]

Similar to the previous cases, $(a^3)$ is of the form $(9k' + 8)$, where $(k')$ is an integers.

In all three cases, $(a^3)$ can be expressed in the form $(9k')$, $(9k' +1)$, or $(9k' + 8)$ for some integer $(k')$.

This concludes that the cube of any integer $(a)$ is either of the form $(9k)$, $(9k + 1)$, or $(9k + 8)$ for some integer $(k)$ .

X

To prove that two positive integers $(a)$ and $(c)$ leave the same remainder when divided by a positive integer $(n)$ if and only if $(a - c)$ is a multiple of $(n)$ (i.e., $(a - c = nk)$ for some integer $(k)$ ), we can split this into two parts: the forward implication (if $(a)$ and $(c)$ have the same remainder, then $(a - c)$ is a multiple of $(n)$ ) and the reverse implication (if $(a - c)$ is a multiple of $(n)$, then $(a)$ and $(c)$ have the same remainder).

Forward Implication (if $(a)$ and $(c)$ have the same remainder, then $(a - c)$ is a multiple of $(n)$ ):

Let's assume that both $(a)$ and $(c)$ have the same remainder when divided by $(n)$, denoted by $(r)$. Mathematically, this means:

$[a \equiv c \pmod{n}]$

Now, we want to show that $(a - c)$ is a multiple of $(n)$, meaning there exists an integer $(k)$ such that $(a - c = nk$ ).

Starting with $(a \equiv c \pmod{n})$, we can write this as:

$[a = c + kn]$

Now, subtract $(c)$ from both sides:

$[a - c = kn]$

This equation clearly shows that $(a - c)$ is a multiple of $(n)$ because it is equal to $(kn)$ for some integer $(k)$.

Reverse Implication (if $(a - c)$ is a multiple of $(n)$, then $(a)$ and $(c)$ have the same remainder):

Let's assume that $(a - c)$ is a multiple of $(n)$, meaning there exists an integer $(k)$ such that $(a - c = nk)$ .

Now, we want to show that $(a)$ and $(c)$ have the same remainder when divided by $(n)$ .

We can start with the equation $(a - c = nk)$ and add $(c)$ to both sides:

$[a = c + nk]$

Now, we can use the definition of congruence modulo $(n)$. If two numbers $(x)$ and $(y)$ differ by a multiple of $(n)$, then $(x)$ and $(y)$ have the same remainder when divided by $(n)$. In this case, $(a)$ and $(c + nk)$ differ by a multiple of $(n)$ ( $(nk)$ ), so they have the same remainder when divided by $(n)$:

$[a \equiv c + nk \pmod{n}]$

Now, we can subtract $(c)$ from both sides to obtain:

$[a - c \equiv nk \pmod{n}]$

Since $(a - c)$ is a multiple of $(n)$ ( $(a - c = nk)$ ), the right side of the congruence ( $(nk)$ ) is also a multiple of $(n)$ .

$[a - c = nk + r]$ with r< n

Therefore, $(a)$ and $(c)$ have the same remainder when divided by $(n)$ .

In conclusion, we have shown both the forward and reverse implications, which means that two positive integers $(a)$ and $(c)$ have the same remainder when divided by a positive integer $(n)$ if and only if $(a - c)$ is a multiple of $(n)$ (i.e., $(a - c = nk)$ for some integer $(k)$ ).

X: Extended Division Algorithm for Integers

Theorem

Let $a$ and $b$ be integers with $b \neq 0$. Then, there exist unique integers $q$ and $r$ such that:

a = bq + r 

and

 0 ≤ r < |b|.

Proof

Case 1: $b > 0$

1. First, let's consider the case when $(b > 0)$ .

   According to the regular Division Algorithm, there exist unique integers (q_1) and (r_1) such that (a = q_1 \cdot |b| + r_1) and (0 \leq r_1 < |b|).

In this case, we have:

( a = q_1 \cdot |b| + r_1 ) 

( 0 \leq r_1 < |b| )

Since $(|b| = b)$, we can rewrite this as:

( a = q_1 \cdot b + r_1 ) 

 ( 0 \leq r_1 < b )

This satisfies the conditions of the Extended Division Algorithm when $(b > 0)$.

Case 2: $b < 0$

2. Now, let's consider the case when (b < 0).

   Again, according to the regular Division Algorithm, there exist unique integers $(q_2)$ and $(r_2)$ such that $(a = q_2 \cdot |b| + r_2)$ and $(0 \leq r_2 < |b|)$ .

In this case, we have:

[ a = q_2 \cdot |b| + r_2 ]

Since $(|b| = -b)$ , we can rewrite this as:

[ a = q_2 \cdot (-b) + r_2 ]

Now, we need to address the range of $(r_2)$. Since $(0 \leq r_2 < |b|)$, and $(|b| = -b)$, we have:

[ 0 \leq r_2 < -b ]

Now, if we multiply by $(-1)$ to both sides, we get:

[ b < -r_2 \leq 0 ]

This correction aligns with the correct range for $(r_2)$ when $(b < 0)$, and we can continue from here.

Now, we have successfully shown that in both cases, (a = bq + r) holds with $(0 \leq r < |b|)$, which satisfies the conditions of the Extended Division Algorithm.

This completes the proof of the Extended Division Algorithm for integers.

When dividing by 3, the Division Theorem (Theorem 2.1) tells us that for any integer $( b )$ divided by 3, there exists a quotient $( q )$ and a remainder $( r )$ such that:

b = 3q + r,

where $( 0 \leq r < 3 )$. This means the possible values for $( r )$ are:

r = 0, 1, \text{ or } 2.

List of Integers for a Chosen Remainder

Let’s choose $( r = 1 )$ as our remainder. We want to find all integers $( b )$ such that:

b = 3q + 1,

where $( q )$ is any integer.

Examples of Integers with Remainder 1 When Divided by 3

Let’s plug in different integer values for $( q )$ to generate some examples:

• If $( q = 0 )$: $( b = 3 \cdot 0 + 1 = 1 )$
• If $( q = 1 )$: $( b = 3 \cdot 1 + 1 = 4 )$
• If $( q = 2 )$: $( b = 3 \cdot 2 + 1 = 7 )$
• If $( q = -1 )$: $( b = 3 \cdot (-1) + 1 = -2 )$
• If $( q = -2 )$: $( b = 3 \cdot (-2) + 1 = -5 )$

So, the integers that leave a remainder of 1 when divided by 3 form the sequence:

\{ \dots, -5, -2, 1, 4, 7, 10, \dots \}.

General Form of Integers with Remainder 1

In general, any integer of the form:

b = 3q + 1,

where $( q )$ is an integer, will give a remainder of 1 when divided by 3. Thus, the set of all such integers can be described as:

\{ 3q + 1 \mid q \in \mathbb{Z} \}.

This notation represents all integers that, when divided by 3, leave a remainder of 1.