Skip to main content

Euclid's Theorem of divisibility in Number Theory.

I am a PhD student of mathematics. I have complete MS in math from the University of Pakistan and have been writing online since 2020.

Euclid's Theorem of Divisibility .


Euclid's Theorem of Divisibility.


Ancient Greek mathematician Euclid was a mathematician and mathematical physicist. He is known as the "father of geometry" and is best known for the Elements work, which established the foundation for geometry and substantially dominated the subject until the early 19th century. In his work, Euclid proved many theorems, including the Pythagoras theorem.

He also established the concepts of GCD (greatest common divisor) and, successive subtractions, which are today referred to as Euclidean divisions. He is best known for his contributions to geometry, which helped to define how we think about time, space, and shapes. Elements, one of the most well-known books that is still used to teach mathematics today, was written by him and is still praised for its originality and deep thought.

The fact that Euclid's work includes more than just a description of geometry or even mathematics explains why he had such a significant impact. The beliefs of western philosophers have been influenced by his use of logic and emphasis on proof for every theorem up until the present. Number theory has benefited greatly from the work of Greek mathematician Euclid. The most significant of these is Euclid's. In this article we will discuss the important theorem of divisibility which is gave by Euclid

Statement of Euclid's Theorem of Divisibility:

Let a, b ∈ Z, then there exist unique integer q and r such that a = bq+r.


Let A be a set such that A = {a – bx} where x ∈ Z and A is not empty set a – b (-a) ∈ A. If 0 ∈ A then 0 is the least element of A. If 0 is not belong to A then A being a subset of positive integers must have least element let us call its “r”. For some x = q ∈ Z. Where r = a – bq ≥ 0 this implies that r ≥ 0. Now we have to prove that r < b.

Suppose that r ≥ b this implies that r – b ≥ 0 since r = a – bq which is equal to

a – bq – b ≥ 0

= a – b (q+1) ≥ 0

Implies that, r – b ∈ A. Hence, r – b < r

This is contradiction to the fact that r is the least element of A. So, our supposition

r ≥ b is wrong. Hence, r < b. So, 0 ≤ r < b. Since r = a – bq which implies that

a = bq +r where 0 ≤ r < b.

For Uniqueness:

Suppose that a = bq1 + r1 also a = bq+r so,

bq1 + r1 = bq+r by taking the mod on both sides which implies that,

Scroll to Continue

│ bq1 + r1 │ = │ bq+r │ which can be written in the form of

│ bq1 - bq │ = │ r – r1 │put the term │ bq1 - bq │ = 0 which implies that,

│ r – r1 │ = 0 from here r = r1 so, bq +r = bq1 + r.

This implies that the expression is unique.

Remarks from Euclid’s Theorem of Divisibility:

  • If r = 0 then “a” is divisibility by “b”.
  • The positive integer q is called quotient and “r” is called remainder.
  • If r = 0 then b / a and conversely if b / a then r = 0.
  • If b = 2 then r = 0 or 1 its mean that every integer is of the form 2k or 2k+1. From this point we conclude two results,
  1. If integer is of the form 2k+1, then it is called odd integer
  2. If integer is of the form 2k then integer is said to be even integer.



If r = 0 then b /a and conversely if b / a then r = 0.


According to Euclid’s theorem a = bq +r since, r = 0 therefore a = bq where q belongs to set of integers Z. Then by the definition of divisibility b / a.

Conversely suppose that if b / a then there exist an element q belongs to set of integers such that a = bq then by Euclid’s theorem q = bq +r so, bq +r = bq this implies that r = 0.

Hence proved that If r = 0 then b /a and conversely if b / a then r = 0.

Applications of Euclid’s Theorem of Divisibility:

  • Euclid’s Theorem of Divisibility is Used to Find out the Highest common Factor (HCF):

The expression "a = bq + r," where q and r are the positive integers, is used to compute the HCF of two large numbers using Euclid's theorem of divisibility. Here, the integers "a" and "b" are positive and "a > b."

  • Euclid’s Theorem of Divisibility is Used to Find out the Diophantine equations:

Diophantine equations may be solved using the Euclidean theorem.

  • Euclid’s Theorem of Divisibility is Used to Find out the Chinese Remainder Theorem:

The Chinese remainder theorem can be used to find integers that satisfy many congruence’s, and the Euclidean algorithm can be used to build continuing fractions and find accurate rational approximations to real numbers.

This content is accurate and true to the best of the author’s knowledge and is not meant to substitute for formal and individualized advice from a qualified professional.

© 2022 Kinza Javaid

Related Articles