BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Prove that if a and b are integers with b>0, then there exists unique integers q and r satisfying a = q b + r, where 2b≤r<3b.

# Prove that if a and b are integers with b>0, then there exists unique integers q and r satisfying a = q b + r, where 2b≤r<3b.

Solution: The division algorithm guarantees that if a and b are integers with b>0, then there exist unique integers q and r satisfying a = q′ b + r′ with 0≤r′<b.

If we define r = r′ + 2b, then 2b≤r<3b

This trick now, is to define a = q b + r, with 2b≤r<3b.

To do this, we start with the relationship grunted by the division algorithm namely a = q b′ + r′, with 2b≤r′ <3b

Since r = r′ + 2b (or equivalently r′ = r-2b).

We can substitute r-2b for r′ this yields a = q′ b + (r-2b) with 2b≤r′ <3b

This suggests that we can let q = q′ -2.

This yields a = q b +r with 2b≤r′ <3b (Proved)

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...