Math IOQM

Theorem: If a1x1 + a2x2 + .... an.xn = K then this Diophantine equation has a solution if d | K where d = gcd(a1,a2...an). We can note the similarities with Bezout's lemma here. Practice: Which of these Diophantine equations have integer solutions? 1. 21x + 15y = 17 2. 7x + 17y = 27 Theorem: If ax + by = c and d | c, where d = gcd(a,b), then this Diophantine equation has infinitely many solutions, and the solutions are of the form x = x0 + (b/d).k, y = y0 - (a/d).k, where k is integer and (x_0, y_0) are particular solutions of (ax + by = c); and x0, y0 are integers.

Q1. Determine all solutions in the positive integers of 18x+5y=48 S1. y = (48-18x)/5 48-18x = 0 mod 5 3 = 3x mod 5 x = 1 mod 5 x = 1 => y = 6 x >= 6 not possible else y will become negative. what if I had done x = (48 - 5y)/18 in that case 48 = 5y mod 18 => 12 = 5y mod 18 Now, the thing is that y mod 18 can range from 0 to 17, so my trial and error will take much longer. So for these kind of equations it's always better to go for a smaller modulus, as we did in the first approach. Q2. 5x+3y=52. S2. x = (52 - 3y)/5 => 2 = 3y mod 5 => y = 4 mod 5 y = 4,9,14 => x = 8, 5, 2 Q3. Find all residues r with 0≤r≤7 such that x^2 ≡r(mod8) has a solution. S3. 0,1,4 Q5. A single bench section at a school event can hold either 7 adults or 11 children. When N bench sections are connected end to end, an equal number of adults and children together will occupy all the bench space. What is the least possible positive integer value of N? S5. a + c = N 7a = 11c 7,11 are primes => s...

 for a,b positive integers if ab+ 1 = k^2 i.e. perfect square then if we use c = a + b + 2k then bc + 1 and ac + 1 will also be perfect squares.

A Diophantine equation is any equation of the form f ( x 1 , x 2 , x 3 , … , x n ) = 0 f(x_1, x_2, x_3, \dots, x_n) = 0 where: f f is a polynomial with integer coefficients, the variables x 1 , x 2 , … , x n x_1, x_2, \dots, x_n are required to take integer values , and usually n ≥ 1 n \geq 1 (not necessarily n ≥ 2 n \geq 2 ). If f f is polynomial with integer coefficients, then it is called an algebraic Diophantine equation . Ex: Determine the number of integers 'n' for which n^2 + 19n + 92 is square. Let n^2 + 19n + 92 = k^2 n^2 + 2.(19/2).n + 92 = k^2 (19/2)^2 = 361/4 92 - 361/4 = 7/4 =>  n^2 + 2.(19/2).n + 361/4 + 7/4 = k^2 => (n + 19/2)^2 = k^2 - 7/4 => (2n + 19)^2 = 4k^2 - 7 => 4k^2 - (2n + 19)^2 = 7 => (|2k| + |2n + 19|) (|2k| - |2n + 19|) = 7 First factor is bigger so: |2k| + |2n + 19| = 7 |2k| - |2n + 19| = 1 Add to get: |2k| = 4 and |2n + 19| = 3 =>  2n + 19 = -+3 => 2n = -19 -+ 3 => n = -11,-8 = Answer Q. Find all unorder...

For e.g., solve for a,b given that they are integers. a^2 - b^2 = 15 (a + b) (a-b) = 15 Here we will compute all the possible factors of 15 and equate one by one. 15 =  x.y a + b = x a - b = y => a = (x + y)/2, b = (x-y)/2 x,y = 1,15 => a,b = 8,-7 x,y = 3,5 => a,b = 4,-1 x,y = 5,3 => a,b = 4,1 x,y = 15,1 => a,b = 8,7 Now negative factors: x,y = -1,-15 => a,b = -8,7 x,y = -3,-5 => a,b = -4,1 x,y = -5,-3 => a,b = -4,-1 x,y = -15,-1 => a,b = -8,-7 In summary: (-+8,-+7) and (-+4,-+-1) Let's see how could we have achieved the same thing easily. a^2 - b^2 = 15 can be written as: |a|^2 - |b|^2 = 15 since a^2 = |a|^2 Rewrite it like this: (|a| + |b|)(|a| - |b|) = 15 This forces |a| > |b| else the signs won't match in LHS and RHS. So both factors are positive now. Let x = |a| + |b| and y = |a| - |b| This forces x > y. Again: |a| = (x + y)/2 and |b| = (x-y)/2 So we just repeat the earlier exercise with positive factors and x > y only: x,y = 5,3 => |...

  "Complete the Rectangle" , also called Simon’s Favorite Factoring Trick , is a clever algebraic method for factoring expressions of the form: x y + a x + b y + c xy + ax + by + c Or more commonly, you'll see it used in a simpler form: x y + a x + b y + d xy + ax + by + d But especially when we’re given something like: x y + a x + b y + a b xy + ax + by + ab It becomes very easy to factor. Let me walk you through it step-by-step. 💡 The Key Idea We add and subtract a constant to turn the expression into a perfect rectangle (a.k.a. a factorable quadratic or product of binomials). The “complete the rectangle” version of this trick usually works best on expressions like: x y + a x + b y + a b xy + ax + by + ab We treat it like this: x y + a x + b y + a b = ( x + b ) ( y + a ) xy + ax + by + ab = (x + b)(y + a) ✅ Step-by-Step Example Factor: x y + 3 x + 2 y + 6 xy + 3x + 2y + 6 Step 1: Rearrange the terms: Group like this: x y + 3 x + 2 y + 6 xy + 3x + ...

Question: 3x + 7y = 100 x,y are positive integers. How many pairs of x,y are possible? Solution: Given that x,y >= 1. So 7y < 100 y < 100/7 y <= 14 So 1 <= y <= 14. Now 3x = 100 - 7y If you put all the values of y one by one you see that RHS becomes divisible by 3 for y = 1,4,7,10,13. So answer is 5 such pairs are there. But why did we choose y for iterating and not x? Let's do it with x. 3x < 100 => x <= 33 So we would have to iterate 33 times and check for divisibility by 7 each time. So it is wiser to go for y. We can make the solution much simpler using modulo arithmetic . 3x = 100 - 7y Do modulo by 3 on both sides. 3x % 3 = (100 - 7y) %3 0 = 100 % 3 - 7y %3   %3 0 = 1 - (7 %3) (y%3) %3 0 = 1- 1.y % 3 y = 1 % 3 Since y goes from 1 to 14, there are 5 values which leave the remainder 1 when divided by 3.

  Below is exactly the chain-of-thought I would go through if this dropped onto my scratch paper in a contest or an exam. I’m writing it slowly so you can see the cues that tell me *what* to complete the square in and *why* those particular shifts appear. --- 1. Look for a **single-variable** square you can force The moment you see a quadratic in two variables, $$ x^{2}+4y^{2}-2xy-2x-4y-8=0, $$ pick one variable (almost always the one with coefficient 1 in its squared term, because that makes the algebra cleaner). Here $x^{2}$ already has coefficient 1, so treat **$y$ as a constant** for a moment and complete the square in **$x$** exactly the way you would in one-variable algebra. Write the $x$-part together: $$ x^{2} \;-\; 2xy \;-\; 2x. $$ It’s a quadratic in $x$ whose linear coefficient is $-2(y+1)$. So $$ x^{2}-2(y+1)x \;=\; \bigl(x-(y+1)\bigr)^{2} \;-\;(y+1)^{2}. $$ > **Why $y+1$?** > Because the standard completing-the-square move says: $x^{2} - 2px = (...

10. What is the greatest possible perimeter of a right-angled triangle with integer side lengths if one of the sides has length 12? Solution: If we have to maximize the perimeter, we should not keep 12 as the hypotenuse. That way hypotenuse will be longer than 12 and the perimeter will be more as compared to keeping 12 as hypotenuse. Let hypotenuse be y and the other leg be x. x^2 + 12^2 = y^2 y^2 - x^2 = 144 (y + x)(y - x) = 144 Since x,y are both integers the problem now reduces to finding integer factors of 144. Let's try them one by one. y + x = 144 y - x = 1 => 2y = 145 => y  = 72.5, x = 71.5, not integer move on. y + x = 72 y - x = 2 => 2y = 74 => y = 37, x = 35 valid solution y + x = 48 y - x = 3 => 2y = 51 => y = 25.5, x = 22.5, not integer move on. Should we try more factors now? Not really. Even if x,y solve for integer values, their values are constantly decreasing as the factors are becoming smaller. So y = 37, x = 35 is the right answer. Perimeter = 3...

Preparation: 1.  If x + y = 130 and their gcd is 10 find all possible pairs of (x,y). Given that x,y are positive integers(natural numbers). 2. If xy = 7 + x + y and x,y are positive integers find the pairs (x,y) satisfying this equation. 3. Complete a rectangle method. How do you factorize axy + bx + cy = d? Solution: Multiply both sides by a => a^2xy + abx + acy = ad => ax(ay + b) + acy = ad => ax(ay + b) + ay(c) = ad => ax(ay + b) + (ay + b)(c) - bc = ad => (ax + c)(ay + b) = ad + bc Now coming to the main question: 11. For natural numbers  x  and  y , let  ( x , y )  denote the greatest common divisor of  x  and  y . How many pairs of natural numbers  x  and  y  with  x ≤ y  satisfy this equation: xy = x + y + (x,y) Solution: Let gcd(x,y) = d xy = x + y + d xy - x - y = d (x-1)(y-1) = d + 1 Let a,b co primes such that, x = ad, y = bd Since x <= y, it means that a <= b. Also a,b are natur...

Let Akbar and Birbal have n marbles, where n>0. Akbar says to Birbal, "If I give you some marbles you will have twice as many as I will have." Birbal says to Akbar, "If I give you some marbles you will have thrice as many as I will have." What is the minimum possible value of n for which the above statements are true? Solution: Suppose Akbar gives Birbal some marbles leaving Akbar with k marble and Birbal with 2k marbles. This implies that n=k+2k for some integer k i.e. n is divisible by 3. Similarly, after Birbal gives Akbar some marbles leaving Birbal with m marbles and Akbar with 3m marbles, we have that n=m+3m=4m for some integer m, i.e. n is divisible by 4. So minimum value of n = LCM(3,4) = 12. Source