Prove that for every positive integer n there exists integer

Prove that for every positive integer n, there exists integers a and b such that 4a2 9b2 -1 is divisible by n.

Solution

Proof :

First, we consider the case when n is odd.

In this case, let b = 0 and let a be any integer satisfying 2a 1 mod n.

Then we have 4a² + 9b² - 1 = 4a² - 1 = (2a + 1)(2a - 1) which is divisible by n .

Now we consider the case when n is not divisible by 3.

In this case, let a = 0 and let b be any integer satisfying 3b 1 mod n.

Then we have 4a² + 9b² - 1 = 9b² - 1 = (3b + 1)(3b - 1) which is divisible by n.

Finally, we consider the general case. We can express n as n₁n₂ where n₁ is not divisible by 2, and n₂ is not divisible by 3, and n₁ and n₂ are relatively prime. (For example, let n₂ be the power of 2 in the prime factorization of n , and let

n₁ be the rest of the prime factorization of n.)

From the first paragraph, there are integers a₁ and b₁ such that 4a₁² + 9b₁² - 1 is divisible by n₁.

From the second paragraph, there are integers a₂ and b₂ such that 4a₂² + 9b₂² - 1 is divisible by n₂.

By the Chinese Remainder Theorem, there is an integer a that is a₁ mod n₁ and a₂ mod n₂ .

Similarly, there is an integer b that is b₁ mod n₁ and b₂ mod n₂ .

Modulo n₁, we have

4a² + 9b² - 1 4a₁² + 9b₁² - 1 0 ( Mod n₁ )

Modulo n₂, we have

4a² + 9b² - 1 4a₂² + 9b₂² - 1 0 ( Mod n₂ )

Thus 4a² + 9b² - 1 is div isible by both n₁ and n₂ .Because n₁ and n₂ are relatively prime, that means 4a² + 9b² - 1

is divisible by their product n₁ n₂   which is n . Hence the proof.