Let $a$, $b$, $c$ and $d$ be integers such that $ac$, $bd$ and $bc+ad$ are divisible with positive integer $m$. Show that numbers $bc$ and $ad$ are divisible with $m$
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2012
Tags: number theory, Divisibility
25.09.2018 19:00
$m|ac\wedge m|bd\wedge m|bc+ad\implies m|(a+b)(c+d)$ as after opening brackets we get the sum of terms divisible by $m$ If one of $a,b,c,d$ is zero theorem is true. Assume they are all non zero. If $m=1$ theorem is obviously true. Assume now $m>1$. Consider any prime $p$ being a divisor of $m$. If you don't know what the following notation means, go for p-adic valuation. It's obvious from definition, that for any integer $x,y\in Z\setminus\lbrace0\rbrace\ v_p(x+y)=\min\lbrace v_p(x),v_p(y)\rbrace\wedge v_p(xy)=v_p(x)+v_p(y)$ $m|(a+b)(c+d)\implies v_p(m)\le v_p(a+b)+v_p(c+d)=\min\lbrace v_p(a),v_p(b)\rbrace+\min\lbrace v_p(c),v_p(d)\rbrace\le v_p(b)+v_p(c)=v_p(bc)$ Repeating this for all primes $p|m$ we get $m|bc$. $m|(a+b)(c+d)\implies v_p(m)\le v_p(a+b)+v_p(c+d)=\min\lbrace v_p(a),v_p(b)\rbrace+\min\lbrace v_p(c),v_p(d)\rbrace\le v_p(a)+v_p(d)=v_p(ad)$ Repeating this for all primes $p|m$ we get $m|ad$.
25.09.2018 20:12
In general the inequality $v_p(a+b)=\min (v_p(a),v_p(b))$ is not true. Consider e.g. $p=2$, $a=2$, $b=6$.
25.09.2018 23:04
The correct is $v_p(a+b)\ge \min\lbrace v_p(a),v_p(b)\rbrace$
25.09.2018 23:37
Lemma: If $m|x+y,m|x^2+y^2$, then $m|2x^2,2y^2$. $m|x+y$ $m|x^2+y^2$ $m|x^2+xy$ $m|y(x-y)$ $m|xy+y^2$ $m|x(x-y)$ $m|(x+y)(x-y)$ $m|x^2-y^2$ $m|x^2+y^2$ $m|2x^2$ Now, $m|bc+ad$ $m|(bc+ad)^2$ $m|b^2c^2+a^2d^2+2abcd$ $m|b^2c^2+a^2d^2$ By Lemma, $m|2b^2c^2,2a^2d^2$. Now, $m|bc+ad$ $m|bc^2+acd$ $m|bc^2$ $m|b^2c+abd$ $m|b^2c$ $m^2|b^3c^3$ But $m|2b^2c^2$ Therefore $m|\frac{bc}2$, thus $m|bc$.
26.09.2018 15:15
Let $p^{k}||m$, where $p$ is a prime, then $p^{k}|ac$, $p^{k}|bd$, and $v_{p}(abcd)\ge 2k$. If $v_{p}(bc)<k$, then $v_{p}(da)<k$, and $v_{p}(bcda)<2k$, a contradiction. We have $v_{p}(bc)\ge k$, and then $v_{p}(da)\ge k$, so $p^{k}|bc$ and $p^{k}|da$ .
26.09.2018 16:21
DynamoBlaze wrote: Therefore $m|\frac{bc}2$ I don't know how can you say that. Consider $b=c=1$.
27.09.2018 20:22
WolfusA wrote: DynamoBlaze wrote: Therefore $m|\frac{bc}2$ I don't know how can you say that. Consider $b=c=1$. If $b=c=1$, then $m|a,d, ad+1$. $m=1$.
30.09.2018 22:59
Yes, but your solution isn't true for cases, when $b,c$ aren't divisible by $2$. I guess you did something like that: $m^2|b^3c^3\wedge m|2b^2c^2\implies m|\frac{bc}{2}$. I don't know how, but it's not true!