Proving the Existence and Uniqueness of Integers q and r in Modular Arithmetic

Introduction

This article discusses the mathematical proof of a fundamental principle in number theory: given an integer a and a non-zero integer b, there exist unique integers q and r such that a bq r and where -1/2b ≤ r ≤ 1/2b.

Proof of Existence of q and r

Consider the following steps while proving the existence of integers q and r that satisfy the above condition:

Division Algorithm

The standard division algorithm states that for any integer a and any non-zero integer b, there exist unique integers q and r such that:

a bq r

where 0 ≤ r b

Our objective is to adjust r to fit the condition -1/2b ≤ r ≤ 1/2b.

Adjustment of r to Fit the New Range

Let's consider two cases:

If r 1/2b

If r ≥ 1/2b

In each case, we will adjust r and q accordingly to ensure that -1/2b ≤ r ≤ 1/2b.

Case 1: If r 1/2b

Set r r initially. If r is greater than 1/2b, we adjust r as:

r r - b

and

q q 1

This adjustment ensures that r is within the desired range.

Case 2: If r ≥ 1/2b

In this case, we need to verify that adjusting r to r - b results in:

r ≥ -1/2b

r b

After adjustment:

r r - b

gives

r ≥ -1/2b - b (since r ≥ 1/2b)

which simplifies to

r ≥ -3/2b

and since -3/2b 1/2b is not possible, we verify:

r b

Hence, r is indeed within the range -1/2b ≤ r ≤ 1/2b.

Proof of Uniqueness of q and r

Assume there exist two pairs (q1, r1) and (q2, r2) such that:

a bq1 r1

a bq2 r2

where -1/2b ≤ r1, r2 ≤ 1/2b

Equating the two expressions, we get:

bq1 r1 bq2 r2

bq1 - bq2 r2 - r1

b(q1 - q2) r2 - r1

Since -1/2b ≤ r1, r2 ≤ 1/2b, the difference r2 - r1 is bounded:

-b ≤ r2 - r1 ≤ b

This implies that:

-b ≤ b(q1 - q2) ≤ b

-1 ≤ q1 - q2 ≤ 1

If q1 ≠ q2, then q1 - q2 ≥ 1. However, this would mean:

b(q1 - q2) ≥ b

which contradicts the bound

-b ≤ b(q1 - q2) ≤ b

Thus, q1 q2 and consequently r1 r2. This proves the uniqueness of q and r.

Conclusion

Therefore, we conclude that there exist unique integers q and r satisfying:

a bq r

where -1/2b ≤ r ≤ 1/2b

This principle is fundamental in the study of number theory and has wide-ranging applications in mathematics and computer science.