mozaMedical by Mozaik Education

Divisibility

The quotient of two integers is not always an integer.

DEFINITION: When considering integers \latex{ a } and \latex{ b } we say that number \latex{ a } is a factor of number \latex{ b }, if there is an integer \latex{ c } for which \latex{a\times c=b}.
Notation: \latex{a\mid b}.

The properties of divisibility

\latex{a\mid a}, since \latex{a\times 1=a}. So every number is a factor of itself.

If \latex{a\mid b}, then \latex{a\mid b \times c}.This hypothesis means that there is a positive integer \latex{d} for which \latex{b=a\times d}, but then \latex{b\times c=a\times (d\times c)} which means \latex{a\mid b\times c}. So if \latex{ a } is a factor of \latex{ b }, then it is also a factor of the multiples of \latex{ b }.

If \latex{a\mid b} and \latex{b\mid c}, then \latex{a\mid c}. The two hypotheses mean that there are positive integers \latex{ d } and \latex{ e } for which \latex{b =a\times d} and \latex{c = b \times e}, therefore \latex{c = b \times e = a \times (d \times e)} which means \latex{a\mid c}.

If \latex{a\mid b} and \latex{a\mid c}, then \latex{a\mid b\pm c}. According to the hypotheses there are positive integers \latex{d} and \latex{e} for which \latex{b = a \times d} and \latex{c = a \times e}. Thus \latex{b ± c = a \times (d ± e)}, which means \latex{a\mid b ± c}. So if a number is a factor of two numbers, then it is also a factor of their sum and of their difference.

If \latex{a\mid b +c } and \latex{a\mid b}, then \latex{a\mid c}. According to the hypotheses there exist integers \latex{d} and \latex{e} for which \latex{b + c = a \times d} and \latex{b = a \times e}.
Thus \latex{c = (b + c) – b = a \times d\, –\, a\times e =a\times (d\, –\, e)}, which means \latex{a\mid c}. So if a number is a factor of a sum and of one of the terms of this sum, then it is also a factor of the other term.

If \latex{a\mid b} and \latex{a\nmid c}, then \latex{a\nmid b + c}. If \latex{a\mid b + c} was true, then because of (5) \latex{a\mid c} would be true, which is not possible, thus \latex{ a } is not a factor of \latex{b + c}.

If for natural numbers \latex{a,\, b} it is true that \latex{a\mid b} and \latex{b\mid a}, then \latex{a = b}. The first hypothesis implies that \latex{ a\leq b}, according to the second one \latex{b \leq a}. Both are fulfilled at once if \latex{a = b}.

For any integer \latex{a\mid 0}, since \latex{0 \times a = 0}. All natural numbers are factors of \latex{0}. It also means that \latex{0} is an even number. \latex{0} has only one multiple which is \latex{0}, but \latex{0} is the multiple of any integer.

For example: \latex{4\mid 12a+(4a)^{2}–\,16}, if \latex{a} is an integer, because \latex{ 4 } is a divisor of every term, but \latex{4\mid 24k+4k^{4}–\,3} is not true, if \latex{ k } is an integer, because the first two terms are divisible by \latex{ 4 }, but the third one is not.

Example 1

Let us prove that if \latex{a} and \latex{b} are integers and \latex{5\mid 2a + 3b}, then \latex{5\mid 16a + 9b}.

Solution

Let us do the following transformation:

\latex{16a + 9b = 6a + 9b + 10a = 3(2a + 3b) + 10a}.

According to the hypothesis, the sum in the brackets is divisible by \latex{ 5 }, and as \latex{ 10a } is also divisible by \latex{ 5 }, the statement is true. (There are infinitely many number pairs \latex{ a;\, b } for which it is true that \latex{5\mid 2a + 3b}, e.g. \latex{a = 1}; \latex{b = 1} or \latex{a = 4}; \latex{b = 4}, etc.)

Rules of divisibility

From the point of view of divisibility, positive and negative integers act in the same way; therefore, we are going to examine the properties of divisibility only for natural numbers.

Example 2

Which numbers of the decimal system are divisible by \latex{ 2 } and which are divisible by \latex{ 5? }

Solution

Every number of the decimal number system can be expressed as the sum of powers of \latex{ 10 }, for example \latex{23,571= 2 ×10^{4}+ 3×10^{3}+ 5×10^{2}+ 7×10 +1}. Except for the last term \latex{ 10 } appears in each term of the sum, and \latex{ 10 } is divisible by \latex{ 2 } and \latex{ 5 }. It depends on the last term of the sum whether the number is divisible by \latex{ 2 } or \latex{ 5 } respectively.

So a number written in the decimal system is divisible by \latex{ 2 } if and only if its last digit is divisible by \latex{ 2 }.

A number written in the decimal system is divisible by \latex{ 5 } if and only if its last digit is divisible by \latex{ 5 }.

Example 3

Which numbers of the decimal number system are divisible by \latex{ 4? }

Solution

Since \latex{ 100 } is divisible by \latex{ 4 }, every power of \latex{ 10 } with an index greater than \latex{ 2 } is also divisible
by \latex{ 4 }.

For example, in the case of the sum \latex{23,571 = 2 × 10^{4}+ 3× 10^{3}+ 5× 10^{2} + 7× 10 + 1} it is enough to examine the last two terms only, \latex{ 71 } is not divisible by \latex{ 4 }, so \latex{ 23,571 } is not divisible by \latex{ 4 } either.

A number written in the decimal system is divisible by 4 if and only if the two-digit number constituted from the last two digits is divisible by \latex{ 4 }.

Example 4

Which numbers of the decimal system are divisible by \latex{ 3 } and which are divisible by \latex{ 9? }

Solution

The powers of \latex{ 10 } can be expressed in the following way:
\latex{ 10 = 9 + 1; 100 = 99 + 1; 1,000 = 999 + 1 }; … etc.

The first terms of the sums are divisible by \latex{ 3 } and \latex{ 9 }, the number standing
in the place corresponding to the respective place value should be multiplied
by the second term (\latex{ 1 }). For example:

\latex{23,571 = 2 × 10^{4} + 3× 10^{3} + 5× 10^{2} + 7×10 + 1=}
\latex{=2× (9,999 + 1) + 3 × (999 + 1) + 5× (99 + 1) + 7 × (9 + 1) + 1}.

It is enough to examine the sum of the digits since the other terms are divisible by \latex{ 3 } and \latex{ 9 }:
\latex{ 2 + 3 + 5 + 7 + 1 = 18 }. Since it is divisible by \latex{ 3 } and \latex{ 9 }, so the original number is also divisible by \latex{ 3 } and \latex{ 9 }.

A number of the decimal system is divisible by \latex{ 3 } or \latex{ 9 } respectively if and only if the sum of the digits is divisible by \latex{ 3 } or \latex{ 9 } respectively.

by \latex{ 2 }, by \latex{ 5 },
by \latex{ 10 }

by \latex{ 3 }, by \latex{ 9 }

based on the sum of the digits

D I V I S I B I L I T Y

by \latex{ 4 }, by \latex{ 25 },
by \latex{ 50 }, by \latex{ 100 }

based on the last two digits

based on the last digit

Example 5

Which numbers of the decimal system are divisible by \latex{ 11? }

Solution

Let us express the powers of \latex{ 10 } with the help of \latex{ 11 }.

\latex{10 = 11-1};
\latex{100 = 9× 11 + 1};
\latex{1,000 = 1,001-1 = 91× 11 \,–\, 1};
\latex{10,000 = 9,999 + 1 = 909×11 + 1}

and so on. The regularity which we can discover shows that a number is divisible by \latex{ 11 } if and only if the sum resulting when adding up the digits with alternating signs is divisible by \latex{ 11 }.

For example \latex{11\mid13,618}, since \latex{8-1 + 6\,-\, 3 + 1 = 11} is divisible by \latex{ 11 }.
\latex{ 34,285 } is not divisible by \latex{ 11 }, because \latex{5 - 8 + 2 - 4 + 3 = -2}.

Based on the above methods we can decide not only whether a number is divisible by \latex{ 2;\, 5;\, 4;\, 3;\, 9, } but also what remainder the number leaves when divided by these numbers.

For example \latex{ 84,137 } leaves \latex{ 1 } as a remainder when divided by \latex{ 4 } because of \latex{ 37 }. Since \latex{8 + 4 + 1 + 3 + 7 = 23}, therefore the remainder is \latex{ 2 } when divided by \latex{ 3 }, and the remainder is \latex{ 5 } when divided by \latex{ 9 }.

Example 6

Let us prove that \latex{5\mid5,324^{2,000} -2,371^{3,000}}.

Solution

Let us examine the powers of numbers ending with \latex{4}: \latex{4^{2} = 16}; \latex{4^{3} = 64}; \latex{4^{4} = 256}; \latex{4^{5} = 1,024}; ….
We can realise that the numbers end with \latex{ 6 } when raised to even index, and end with \latex{ 4 } when raised to odd index.
According to this the power \latex{5,324^{2,000}} ends with \latex{ 6 }, and leaves \latex{ 1 } as a remainder when divided by \latex{ 5 }.
If the last digit of a number is \latex{ 1 }, then all powers of it end with \latex{ 1 }, thus power \latex{2,371^{3,000}} leaves \latex{ 1 } as a remainder when divided by \latex{ 5 }.
Since both numbers leave \latex{ 1 } as a remainder when divided by \latex{ 5 }, their difference is divisible by \latex{ 5 }.

Note: Realise that \latex{5\mid5,324^{2,000} -2,371^{3,000}}, but \latex{5\nmid5,324^{2,000}} and \latex{5\nmid 2,371^{3,000}}. Based on this we can say that the converse of property (\latex{ 4 }) of divisibility is not true, which means \latex{a\mid{b}-c\nRightarrow a\mid b } and \latex{a\mid c}.
From a different approach we can also say that number \latex{ a } being a factor of both \latex{ b } and \latex{ c } is a sufficient but not necessary condition of number a being a factor of difference \latex{b\, –\, c}. (The same holds for the sum too.)

The numbers leaving \latex{m} as a remainder when divided by \latex{ 5 } have the form of \latex{5k+m\, (k\in \Z)}. If two numbers leave the same remainder when divided by \latex{ 5 }, then their difference is divisible by \latex{ 5 }, because \latex{5k+m- (5l+m)=}

\latex{=5(k - l)\, (k, l \in \Z)}.

If \latex{b} and \latex{c} leave the same remainder when divided by \latex{ a }, then \latex{b - c} is divisible by \latex{ a }. If \latex{ b } and \latex{ c } leave such remainders when divided by \latex{ a } the sum of which is \latex{ a }, then \latex{b + c} is divisible by \latex{ a }.

Prime numbers, composite numbers

Example 7

Let us find the factors of the following numbers: \latex{ 12;\, 21;\, 13;\, 31;\, 1 }.

Solution

factors of \latex{ 12 }

factors of \latex{ 21 }

factors of \latex{ 31 }

factor of \latex{ 1 }

factors of \latex{ 13 }

\latex{ 1; 2; 3; 4; 6; 12 }

\latex{ 1; 3; 7; 21 }

\latex{ 1; 13 }

\latex{ 1; 31 }

\latex{ 1 }

⯁ ⯁ ⯁

DEFINITION: Those positive integers, which have exactly two positive divisors, are called prime numbers.

Such numbers are, for example \latex{ 2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; … }

DEFINITION: Those positive integers, which have more than two positive divisors, are called composite numbers.

Composite numbers are, for example, \latex{ 4; 6; 8; 9; 10; 12; 14; 15; 16; 18; 20; …; 2,000; … }

Number \latex{1} is neither a prime nor a composite number.

THEOREM: There are infinitely many prime numbers.

Proof

Let us assume that the above statement is not true, i.e. the number of prime numbers is finite. Let the prime numbers then be: \latex{p_1, p_2, p_3, …, p_n}.

Let us constitute the following number: \latex{A=p_{1}\times p_{2}\times p_{3}\times ...\times p_{n}+ 1}.

None of the listed primes is a factor of number \latex{ A }. Thus, either number \latex{ A } is a prime, or it has a prime factor, which was not listed above. It is true in both cases that we found a new prime number, so it cannot be true that there are finitely many prime numbers. And if it is not true, then there are infinitely many prime numbers.

Note: The proof process, where we show that the negation of the statement is false, is called proof by contradiction.

⯁ ⯁ ⯁

Let us express \latex{ 2,000 } as a product of prime numbers:

\latex{2,000 = 2 \times 1,000 = 2 \times 2 \times 500 = 2\times 2 \times 2 \times 250 = 2\times 2 \times 2 \times 2 \times 125 =}
\latex{= 2\times 2 \times 2 \times 2 \times 5 \times 25 = 2\times 2 \times 2 \times 2 \times 5 \times 5 \times 5 = 2^4 \times 5^3}

It is also true generally:

THE FUNDAMENTAL THEOREM OF ARITHMETICS: Any composite number can be factorised as a product of prime numbers independently of the order of factors.

For example: \latex{1,956 = 2^{2} ×3× 163}; \latex{2,200 = 2^{3} ×5^{2} × 11}; \latex{14,625 = 3^{2} ×5^{3} × 13}.

When factorising as a product the rules of divisibility help. (In function tables the prime factorisation of some numbers not divisible by \latex{ 2, 3 } and \latex{ 5 } can also be found.) The prime factor of a number should be looked for until we reach the square root of the number, if there is no such factor, then the number is a prime.

Example 8

How many positive factors does \latex{ 2,700 } have?

Solution

The prime factorisation is: \latex{2,700 = 2^{2} × 3^{3} ×5^{2}}. It follows from this that the prime factorisations of the factors of \latex{ 2,700 } can contain only primes \latex{ 2, 3 } and \latex{ 5 }, and \latex{ 2 } can be raised to the power of two at most, \latex{ 3 } can be raised to the power of three at most, and \latex{ 5 } can be raised to the power of two at most. It can also happen that the factor does not contain all these primes.

Let us summarise the options in a table.

The prime factorisation of a factor is generated by picking one number from all three columns and then by multiplying the three picked numbers. Since we can pick from the first and the third column in \latex{ 3 } and \latex{ 3 } ways respectively, and for every selection we have \latex{ 4 } options to pick a power from the middle column, therefore, \latex{ 2,700 } has a total of \latex{3 × 4 ×3 = 36} divisors.

It is also true generally:

P R I M E N U M B E R S

\latex{ 2 }

\latex{ 3 }

\latex{ 5 }

\latex{ 1 }

\latex{ 2 }

\latex{ 2^{2} }

\latex{ 5^{2} }

\latex{ 5 }

\latex{ 1 }

\latex{ 3 }

\latex{ 3^{2} }

\latex{ 3^{3} }

I

N

D

E

X

0

\latex{ 1 }

\latex{ 2 }

\latex{ 3 }

If the prime factorisation of composite number \latex{a} is

\latex{a=p^{r_{1} }_{1} \times p^{r_{2} }_{2}\times ...\times p^{r_{k} }_{k}},

then the number of divisors of number \latex{a} is:

\latex{(r_{1}+1 )\times (r_{2}+1 )\times ...\times (r_{k}+1 )}.

Example 9

Give the number of odd factors of \latex{ 252,000 }.

Solution

Its prime factorisation is: \latex{252,000 = 2^{5} × 3^{2} × 5^{3} × 7}. The factors which do not contain number \latex{ 2 } are the factors of \latex{3^{2} × 5^{3} × 7}, their number is \latex{(2 + 1)\times (3 + 1)\times (1 + 1) = 24}.

Therefore, \latex{ 252,000 } has \latex{ 24 } odd factors.

Exercises

{{exercise_number}}. Prove that a number written in the decimal system is divisible by \latex{ 8 } if and only if the three-digit number formed from the last three digits is divisible by \latex{ 8 }.

{{exercise_number}}. Prove that \latex{10\mid426^{19} + 2^{58}}.

{{exercise_number}}. Prove that \latex{ 3 } is a divisor of the sum \latex{1,516^{40} + 202^{50} + 400^{60}}.

{{exercise_number}}. What digits can be written instead of \latex{ x } and \latex{ y } if

\latex{15\mid \overline{5x\;327y}};

\latex{12\mid \overline{5x \;327y}?}

{{exercise_number}}. Prove that if \latex{ a } and \latex{ b } are natural numbers and \latex{17\mid a + 2b}, then \latex{17\mid 20a + 6b}.

{{exercise_number}}. Is there a prime number \latex{ p } for which \latex{p + 7} is also a prime number?

{{exercise_number}}. Is there a prime number \latex{ p } for which \latex{p + 10} and \latex{p + 14} are also prime numbers?

{{exercise_number}}. Number \latex{ n } leaves \latex{ 1 } as a remainder when divided by \latex{ 4 }, number \latex{ k } leaves \latex{ 2 } as a remainder when divided by \latex{ 4 }. Give the remainder of the following numbers when divided by \latex{ 4 }.

\latex{n+k}

\latex{k\times n}

\latex{2n+k}

{{exercise_number}}. Number \latex{ m } is odd, and leaves \latex{ 2 } as a remainder when divided by \latex{ 3 }.

What is the remainder if \latex{ m } is divided by \latex{ 6? }
What can the remainder be if \latex{ m } is divided by \latex{ 12? }

{{exercise_number}}. How many positive factors do the following numbers have: \latex{ 27;\, 48;\, 64;\, 121;\, 500;\, 625? } Which of them have even number of factors?

{{exercise_number}}. What is the smallest positive integer which has \latex{ 10 } factors?

Mathematics 9.

-