Find the least positive integer $n$ satisfying the following statement: for eash pair of positive integers $a$ and $b$ such that $36$ divides $a+b$ and $n$ divides $ab$ it follows that $36$ divides both $a$ and $b$.
Problem
Source: II Caucasus Mathematical Olympiad
Tags: number theory
21.03.2018 02:47
Hmm I’m probably wrong but here: Let x and y be the remainders when you divide a and b by 36, respectively. We know x+y = 0, and we want x = 0, y = 0. If we have **xy congruent to 0 (mod 36)**, then we are done (then zero product property says at least one of x and y is 0 and x+y= 0 says the other is also). a and b could potentially be relatively prime to 36 (ex. a = 7, b = 29) so n = 36 for the starred (**) statement to be true
21.03.2018 02:48
Sorry btw I didn’t use Latex - I’m on a cell phone
21.03.2018 04:25
$n=36$ is incorrect, consider $a=6, b=30$. I believe the correct answer is $n=216$ but I do not have a proof.
21.03.2018 13:56
$n=216$ If $216|ab$ then $8|ab$ so $4|a$ or $4|b$ but from $4|a+b$ follows, that $4|a,b$. Same way for $9|a,b$ If $8\not | n$ or $27 \not |n$ we can find contradiction.
21.03.2018 15:27
Oh oops I see where I was wrong now.
23.03.2018 13:38
Happy2020 wrote: Sorry btw I didn’t use Latex - I’m on a cell phone U can put $
25.03.2024 17:23
////...///