Let $\mathbb{N}$ be the set of all positive integers and $S=\left\{(a, b, c, d) \in \mathbb{N}^4: a^2+b^2+c^2=d^2\right\}$. Find the largest positive integer $m$ such that $m$ divides abcd for all $(a, b, c, d) \in S$.
Problem
Source:
Tags: number theory, RMO 2023, Squares, Divisibility
29.10.2023 13:56
It was 12 easy mod bash
29.10.2023 20:12
Notice $a^2, b^2, c^2, d^2 \equiv 0,1\pmod4$. This means that we may only have two cases: One where two of $a^2, b^2, c^2$ divide 4 or where all of them divide 4. So at minimum two of $a, b, c, d$ are even. This means that $4 \mid abcd$. Furthermore, notice $a^2, b^2, c^2, d^2 \equiv 0,1\pmod3$. Hence it is easy to see that at minimum 1 of $a, b, c, d$ will divide 3 in the scenario where $a^2, b^2, c^2 \equiv 1\pmod3$. Therefore $3\mid abcd$. Hence $12\mid abcd$ and we are done This construction is clearly visible by 2,2,1,3
30.10.2023 05:28
ATGY wrote: Notice $a^2, b^2, c^2, d^2 \equiv 0,1\pmod4$. This means that we may only have two cases: One where two of $a^2, b^2, c^2$ divide 4 or where all of them divide 4. So at minimum two of $a, b, c, d$ are even. This means that $4 \mid abcd$. Furthermore, notice $a^2, b^2, c^2, d^2 \equiv 0,1\pmod3$. Hence it is easy to see that at minimum 1 of $a, b, c, d$ will divide 3 in the scenario where $a^2, b^2, c^2 \equiv 1\pmod3$. Therefore $3\mid abcd$. Hence $12\mid abcd$ and we are done Wrong,you have to prove that $12$ is the maximum possible m as well i.e. no integer $\ge 12$ can satisfy this condition. However that is easy since the first case is $(1,2,2,3)$ which yields a product of $12$
30.10.2023 06:45
Wait, shouldn't a,b,c,d be fourth powers ?
30.10.2023 13:06
But it has infinite solutions right ??
30.10.2023 13:07
Sarthak_Agarwal_867 wrote: But it has infinite solutions right ?? If you put a b c d to be even then ...
30.10.2023 13:13
Sarthak_Agarwal_867 wrote: But it has infinite solutions right ?? No, we are to find the largest $m$ that divides $abcd$ for all $(a, b, c, d) \in S$ and notice that the smallest solution for $(a, b, c, d)$ is $(1, 2, 2, 3)$ in which case $abcd = 12$. Hence 12 is the only solution...
30.10.2023 16:24
bump... if a,b,c,d belong to N^4, shouldn't they be fourth power of a natural number. How does a = 2 or 3 work?
30.10.2023 17:06
polynomialian wrote: bump... if a,b,c,d belong to N^4, shouldn't they be fourth power of a natural number. How does a = 2 or 3 work? Just observe that $1^2+2^2+2^2=3^2$ even a naive example contradicts your claim and $N^4$ doesn't mean $a,b,c,d$ are $4$th powers.$N^4$ is used to signify that $(a,b,c,d)$ is a set of $4$ natural numbers. Also @Sarthak_Agarwal yes the equation has infinite solutions,so what?
30.10.2023 17:33
Project_Donkey_into_M4 wrote: polynomialian wrote: bump... if a,b,c,d belong to N^4, shouldn't they be fourth power of a natural number. How does a = 2 or 3 work? Why are you talking so randomly Just observe that $1^2+2^2+2^2=3^2$ even a naive example contradicts your claim and $N^4$ doesn't mean $a,b,c,d$ are $4$th powers.$N^4$ is used to signify that $(a,b,c,d)$ is a set of $4$ natural numbers. Also @Sarthak_Agarwal yes the equation has infinite solutions,so what? i thought belongs to $N^4$ means a,b,c,d belongs to the set of the fourth power of integers. Thanks for clarifying
31.10.2023 14:18
Sol:- Consider tuple $(a^2,b^2,c^2,d^2) \pmod 4$.Since $x^2 \equiv 0,1 \pmod 4$.The only possibilities are $(0,0,0,0);(1,0,0,1);(0,1,0,1);(0,0,1,1)$.So atleast $2$ of $a,b,c,d$ must be even which implies $4|m$. Now consider tuple $(a^2,b^2,c^2,d^2) \pmod 3$.Since $x^2 \equiv 0,1 \pmod 3$.The only possibilities are $(0,0,0,0);(1,0,0,1);(0,1,0,1);(0,0,1,1),(1,1,1,0)$. So atleast one of $a,b,c,d$ is divisible by 3 which implies $3|m$. Hence $12|m$. Since $1^2+2^2+2^2=3^2$ , $(1,2,2,3) \in S \implies m|12$. So $m=12$.
11.11.2023 13:43
Very easy problem, I solved this in contest by first constructing the tuple (1,2,2,3) and then proving that 4 divides m and 3 divides m.
03.02.2024 08:48
First go with primes and power of primes then you will get 2^2 and 3 divides all abcd, then when you will go with 5 then you will get ( 1, 1, 4, 1) combo that will not be divisible by 5 Remaining all primes and their powers will have 0 , 1 , 4 as square module remainders so you will be able to find ( 1, 1, 4, 1) as a combo to ensure they doesnt divide all abcd hence 2^2 and 3 are the only factors So 12 is the answer
14.03.2024 20:12
Claim 1: $m\leq 12$ Proof: Observe that $(1,2,2,3)$ is a solution $\implies m\mid 12 \implies m\leq 12$ Claim 2: $4\mid m$ Proof: $*$ Let us assume that none of the numbers are even. We know that any odd square $\equiv 1 \pmod{4}$ But then $LHS \equiv 3 \pmod{4}$, $RHS \equiv 1 \pmod{4}$, which is not possible. $*$ Now, let us assume that only 1 of $a,b,c,d$ is even. Clearly from the previous argument, it cannot be $d$. Then WLOG, assuming that $a$ is even, rest are odd. Then $LHS \equiv 2 \pmod{4}$, $RHS \equiv 1 \pmod{4}$, which, again is not possible. Therefore, at least two of $a,b,c,d$ are even $\implies \boxed{4 \mid abcd}$. Claim 3: $3\mid m$ Proof: $*$ Any perfect square $\equiv 0,1 \pmod{3}$. Assuming none of the numbers are divisible by $3$, $LHS \equiv 0 \pmod{3}$, but $RHS \equiv 1 \pmod{3}$, which is not possible. $\implies$ at least one of the numbers in divisible by $3 \implies \boxed{3\mid abcd}$. Combining the two, we get that $12\mid abcd$ for such tuples $\implies 12 \mid m$. But $m\mid 12$ also. Therefore, $\boxed{m=12}$ is the required solution!
14.06.2024 19:29
polynomialian wrote: Wait, shouldn't a,b,c,d be fourth powers ? Heyyy Can we be friends??
17.09.2024 18:21
Viewing the equation $\pmod 3$, and $\pmod 4$, we see that atleast one of $a,b,c,d$ must be divisible by $3$ and $4$. Combining these, we get that $12|m$. Now the minimum $m$ is when $(a,b,c,d)$ is $(1,2,2,3)$ which gives $m=12$.
06.10.2024 13:37
Nice But saying at least one of abcd is divisible by 4 is apparantly wrong Instead it were good if said at least two abcd will be divisible by 2
10.10.2024 15:42
My proof is a bit different. WLOG consider $a \ge b \ge c$ First we take $d=1$ and there are no possible solutions. Similary there is no solution for $d=2$ For $ d=3$ the only solution is $ a=2,b=2,c=1$ I can claim that this is the smallest possible set. Hence, $ m\le 12$ $a^2+b^2+c^2=d^2$ multiply this equation by $k^2$ where $k \in Z^+$ $ (ka)^2 + (kb)^2 +(kc)^2 =(dk)^2$ So, $m=k^4abcd$ All the other solutions are going to be the multiplte of abcd which is 12. Hence, $\boxed{m=12}$
16.10.2024 20:38
I have discussed this question in my RMO 2023 video on my channel "little fermat". Here is the Video
02.11.2024 14:31
newton_24 wrote: My proof is a bit different. WLOG consider $a \ge b \ge c$ First we take $d=1$ and there are no possible solutions. Similary there is no solution for $d=2$ For $ d=3$ the only solution is $ a=2,b=2,c=1$ I can claim that this is the smallest possible set. Hence, $ m\le 12$ $a^2+b^2+c^2=d^2$ multiply this equation by $k^2$ where $k \in Z^+$ $ (ka)^2 + (kb)^2 +(kc)^2 =(dk)^2$ So, $m=k^4abcd$ All the other solutions are going to be the multiplte of abcd which is 12. Hence, $\boxed{m=12}$ This is wrong, i think cause you can't characterize all solutions as $2k, k, k, 3k$