Divisibility and primes

 Division Algorithm

Theorem :-

If a and b are integers and b>0, there exist unique integers q and r determined by a and b such that;

a=qb+r,    here r is   0≤r<b.

Division Algorithm

Theorem :-

If a and b are integers and b>0, there exist unique integers q and r determined by a and b such that;

a=qb+r,    here r is   0≤r<b.

Proof;

 

The Division Algorithm is a theorem in number theory that states that given any two positive integers, there exist unique integers, called the quotient and remainder, such that:
 
a = bq + r
 
where a and b are positive integers, q is the quotient, r is the remainder, and 0 ≤ r < b.
 
To prove this theorem, we will first prove the existence of the quotient and remainder, and then prove their uniqueness.
 
Existence:
 
Let a and b be positive integers. We want to show that there exist integers q and r such that a = bq + r and 0 ≤ r < b.
 
We start by setting r = a and q = 0. Then we repeatedly subtract b from r until we obtain a remainder that is less than b. Since we are subtracting b at each step, we can do this at most a times, so we will end up with a remainder r such that 0 ≤ r < b.
 
Let's illustrate this process with an example. Suppose a = 17 and b = 5. We start with r = 17 and q = 0. We subtract 5 from r to get r = 12 and q = 1. We subtract 5 from r again to get r = 7 and q = 2. We subtract 5 from r one more time to get r = 2 and q = 3. Since 2 is less than 5, we stop the process, and we have found the remainder r = 2 and the quotient q = 3. We can check that a = bq + r, since 17 = 5*3 + 2.
 
Uniqueness:
 
Next, we will show that the quotient and remainder we found are unique. Suppose there are two pairs of integers q1, r1 and q2, r2 such that:
 
a = bq1 + r1, 0 ≤ r1 < b
 
a = bq2 + r2, 0 ≤ r2 < b
 
We want to show that q1 = q2 and r1 = r2.
 
Suppose q1 < q2. Then we have:
 
a = bq1 + r1 < bq2 + b
 
which implies:
 
r1 < b - (b - r2) = r2
 
But this contradicts the fact that 0 ≤ r1 < b and 0 ≤ r2 < b. Therefore, q1 cannot be less than q2.
 
Similarly, we can show that q1 cannot be greater than q2, so we must have q1 = q2.
 
Now that we know q1 = q2, we can substitute q1 for q2 in the second equation to get:
 
r1 = a - bq1 = a - bq2 = r2
 
Therefore, we have shown that the quotient and remainder are unique.
 
This completes the proof of the Division Algorithm.

The Division Algorithm is a fundamental result in number theory that states that given two integers a and b, with b not equal to 0, there exist unique integers q and r such that:

 

a = bq + r

 

where 0 ≤ r < |b|. Here, q is the quotient and r is the remainder of the division of a by b.

 

More formally, the Division Algorithm can be stated as follows:

 

Given integers a and b, with b > 0, there exist unique integers q and r such that:

 

a = bq + r

 

where 0 ≤ r < b.

 

The Division Algorithm is a powerful tool for solving a wide variety of problems in number theory and other areas of mathematics. It allows us to compute quotients and remainders efficiently, which is useful in many applications, including cryptography, computer science, and engineering.

 

The proof of the Division Algorithm is typically done using the well-ordering principle, which states that every non-empty set of positive integers has a least element. The idea is to consider the set of all integers of the form a - bq, where q is an integer, and to use the well-ordering principle to show that there exists a least non-negative integer r that can be written in this form. This r is the desired remainder, and the quotient q can be found by dividing a - r by b.