Proving the Existence of Integer Solutions for a Linear Equation

In this article, we are going to prove a fundamental result using basic mathematical techniques, without relying on advanced algorithms like the Euclidean Algorithm. This method is suitable for explaining the concept to a student in their seventh year of education, as it involves logical reasoning and algebraic manipulation.

Introduction

We want to show that for any integer k, there exist integers r and s such that:

22r - 18s 2k

Simplifying the Equation

The first step is to simplify the equation by factoring out a 2 from the coefficients:

22r - 18s 2(11r - 9s)

Thus, we can rewrite the original equation as:

11r - 9s k

Determining the Existence of Integer Solutions

To prove that the equation 11r - 9s k has integer solutions for any integer k, we appeal to a fundamental property of linear Diophantine equations. A linear Diophantine equation of the form:

ax - by c

has integer solutions if and only if the greatest common divisor (gcd) of a and b divides c.

Calculating the GCD

Let's calculate the gcd of 11 and 9. The prime factorization of 11 is just 11 (since it is a prime number), and the prime factorization of 9 is 3^2. Since 11 and 9 share no common factors, their gcd is:

gcd(11, 9) 1

Verifying the GCD Divides k

Since 1 divides every integer k, we can conclude that for every integer k, there exist integers r and s such that:

11r - 9s k

Conclusion

Since we have shown that for every integer k, there exist integers r and s such that 11r - 9s k, we can conclude that:

22r - 18s 2k

also holds for those integers r and s. Therefore, the original statement is proven true:

forall k in mathbb{Z}, exists r, s in mathbb{Z}, 22r - 18s 2k

Alternative Approach for Grade 7 Students

For a simpler explanation, we can solve the basic equation 11r - 9s 1 without using the Euclidean Algorithm. By inspection, we find that:

s frac{1 - 11r}{9} frac{1 - 9r - 2r}{9} frac{1 - 2r}{9} - r

For the equation to have integer solutions, frac{1 - 2r}{9} must be an integer. Setting r 5, we get:

s -6

Thus, one solution to 11r - 9s 1 is r 5 and s -6. Therefore, for any integer k, we have:

r 5k

s -6k

This shows that the equation 11r - 9s k has integer solutions for any integer k.

Conclusion: We have proven that for every integer k, there exist integers r and s such that 22r - 18s 2k using both a formal method and an alternative approach suitable for a seventh-grade student.