IOQM Revision | Beautiful Number Theory Part 2 | Math Olympiad Preparation

Keep learning great Mathematics!

#ioqm #matholympiadpreparation #numbertheory

[RaghavMukhija]

For Challenge 1:
Solve for the diophantine 3x+7y=1
Use Division Algorithm:
7=3(2)+1
Use Division Algorithm In Opposite way:
1=7(1)-3(2)
1=3(-2)+7(1)
OR
3(-2)+7(1)=1

We have got our first set of solutions for (x, y): name it (x*, y*)
Now, for the general solution, we need to use the formula--
(x, y) = (x*+t[b/gcd(a, b)] , y*−t[a/gcd(a, b)) Here a and b are coefficients of x and y respectively.
For some integer t
Substitute values,
(x, y) = (-2+t(7/1), 1-t(3/1))
(x, y) = (-2+7t, 1-3t)

Let's try it out,
t=0 ---- gives solutions (x*, y*) = (2, -1)
t=1 ---- gives solutions (5, -2)
t=2 ---- gives solutions (12, -5)
t=3 ---- gives solutions (19, -8)
t=4 ---- gives solutions (26, -11)

BINGO! There we have 5 solutions for the diophantine equation 3x+7y=1.
Notice that since, the question was only to find 5 solutions not general solutions, we could have randomly inputted values for x to get values for y.

[saurabhsuman]

We can prove challenge 2 easily by modular arithmetic
gcd a, b is d
Now a is congruent to 0 mod d and similarly b
Now multiply x in 1 congruence and y in 2 congruence then add them
Proved