Let $p$ be an odd prime.Positive integers $a,b,c,d$ are less than $p$,and satisfy $p|a^2+b^2$ and $p|c^2+d^2$.Prove that exactly one of $ac+bd$ and $ad+bc$ is divisible by $p$
Problem
Source: China Southeast Math Olympiad 2014 No.1
Tags: modular arithmetic, number theory unsolved, number theory
16.08.2014 21:12
Two equalities kill this problem: $(ac+bd)-(ad+bc)=(a-b)(c-d)$ and $(ac+bd)(ad+bc)=(a^2+b^2)cd+(c^2+d^2)ab$.
20.08.2014 16:01
Observe that $(ac+bd) - (ad + bc) = (a-b)(c-d) \not \equiv 0 \pmod p$, so it follows that $p$ does not divide both expressions. Also, $(ac+bd)(ad+bc) = cd(a^2 + b^2) + ab(c^2 + d^2) \equiv 0 \pmod 4$, so it follows at least one of the two expressions has a factor of $p$. Hence only one of $ac+bd, ad+bc$ has a factor of $p$.
31.10.2024 04:18
Since, It is given to us \[ a,b,c,d < p \] Claim : $p$ doesn't divide both of $(ac+bd)$ and $(ad+bc)$ Proof : FTSOC, let us assume $p$ divides both \[ \implies (ac+bd) - (ad + bc) = (a-b)(c-d) \]But, \[ (a-b)(c-d) \not\equiv 0 \pmod{p} \]And this Proves our Claim! Now, We see \[ (ac+bd)(ad+bc) = (a^2 + b^2)cd + (c^2 + d^2)ab \]and $p$ divides it, which is clearly visible \[ \implies p \mid (a^2 + b^2)cd + (c^2 + d^2)ab \]\[ \implies p \mid (ac+bd)(ad+bc) \]Since, we have proved $p$ doesn't divide both of $(ac+bd)$ and $(ad + bc)$ and here we found $p$ divides $(ac+bd)(ad+bc)$ $\therefore$ $p$ divides any one of $(ac+bd)$ , $(ad+bc)$