Which problem on the test was this?

IAmTheHazard wrote: Which problem on the test was this? Problem 1 (edited to add).

The answer is non-primes. Observe that \(a+b+c+d\mid abc+abd+acd+bcd\) is equivalent to \begin{align*} 0&\equiv abc+(ab+bc+ca)d\\ &\equiv abc-(a+b+c)(ab+bc+ca)\\ &\equiv-(a+b)(b+c)(c+a)\pmod{a+b+c+d}. \end{align*}Note that \(a+b\), \(b+c\), \(c+a\) are each less than \(a+b+c+d\), so the condition cannot hold if \(s=a+b+c+d\) is prime. Moreover, each non-prime \(s=mn\) can be attained by taking \(a=1\), \(b=m-1\), \(c=n-1\), and \(d=(m-1)(n-1)\), so the answer follows.

v_Enhance wrote: Determine all integers $s \ge 4$ for which there exist positive integers $a$, $b$, $c$, $d$ such that $s = a+b+c+d$ and $s$ divides $abc+abd+acd+bcd$. Proposed by Ankan Bhattacharya and Michael Ren Very nice problem.

Sniped BTW 5/10 MOHs?

The answer is all composites. Notice this factors to $ab(c+d)+cd(a+b).$ Also note $a+b\equiv -(c+d)\pmod{s}$ by definition, so this is equivalent to \[ab(a+b)\equiv cd(a+b)\pmod{s}.\] If $s$ is prime, then $\gcd(a+b,s)=1$ as $a+b<s.$ So this implies $ab\equiv cd\equiv -c(a+b+c)\pmod{s}.$ This further simplifies to \[ab+ac+bc+c^2\equiv (c+a)(c+b)\equiv 0\pmod{s}.\]Since $c+a,c+b<s,$ we cannot have $s\mid a+c$ or $s\mid b+c.$ If $s$ is composite, let $s=pq;$ merely take $a=p-1,b=1, c=q-1,=pq-p-q+1=(p-1)(q-1)$ and note that \[p-1\equiv (p-1)(q-1)^2\pmod{q}.\]

Similar to Romania 2014: https://artofproblemsolving.com/community/c1068820h2132571p15598287

Proof that $s$ is not a prime. Suppose that $p=a+b+c+d$ is a prime. We have $0=abc+abd+acd+bcd=ab(c+d)+cd(a+b)=-ab(a+b)+cd(a+b)=(a+b)(cd-ab)(mod p)$ Using the fact that $p$ is a prime bigger than $a+b$, we get that $ab=cd(mod p)$. Thus $abcd=(cd)^2(mod p)$. Analogously $ac=bd(mod p)$ and $ad=bc(mod p)$. This way we obtain $abcd=(cd)^2=(bd)^2=(bc)^2(mod p)$. For example, using $(cd)^2=(bd)^2 (mod p)$ we have that $d^2(c-b)(c+b)=0(mod p)$, which is obviously impossibe (all those numbers are smaller than the prime $p$).

Funny P1. Not too hard but I overcomplicate it. The answer is $\boxed{\text{all composite } s \ge 4}$. Necessity. Suppose otherwise, that $s$ is a prime, then \begin{align*} a + b + c + d &\mid abc + bcd + cda + dab \\ a + b + c + d &\mid (ab + bc + ca)(-a-b-c) + abc \\ a + b + c + d &\mid (ab + bc + ca)(a + b + c) - abc \\ a + b + c + d &\mid (a + b)(b + c)( c+ a) \end{align*}If $s = a + b + c + d$ is a prime, this forces $s \mid a + b , b + c, \ \text{or} \ c + a$. However, WLOG $s \mid a + b$, then this forces $a + b + c + d \mid a + b$, a contradiction. Sufficiency For any composite $s = xy$, where $x,y > 1$, take \[ \left(1, x - 1, y - 1, (x - 1)(y - 1) \right) \]The above is the form of $(1,m,n,mn)$ and this works since \[ (m + 1)(n + 1) \mid mn(m + 1)(n + 1) \] Remark. Here's a bit of motivation. We have something like \[ a + b + c + d \mid abc + abd + acd + bcd \]Therefore, if possible, we want $a,b,c,d$ to be $1$ as many as possible. Trying $(a,1,1,1)$ gives us nothing really helpful. But $(a,a,1,1)$ excluded all even $s$. In particular if we do $(a,b,1,1)$, we could exclude all non-squarefree odd integers. Since we will get something like $a + b + 2 \mid (a + 1)^2$ and $a + b + 2 \mid (b + 1)^2$ -- for which we can just pick $a + 1 = km$ and $b + 1 = kn$, where $m + n \mid k$, and this satisfies. This process forces $(m + n)^2 \mid k(m + n) \mid a + b + 2$, so as long as $s$ is non-squarefree, we can do this. The proof of prime fails come up pretty naturally, and finally the construction $(ab, a,b, 1)$ comes naturally as we start figuring out about things like: \[ \left(1, p - 1, \frac{s}{p} - 1 , s - p - \frac{s}{p} - 1 \right) \]This above construction is motivated by the fact that we get \[ \underbrace{a + b + c + d}_{\text{something squarefree}} \mid (a + b)(b + c)(c + a) \]and therefore we could force a prime $p \mid a + b$ and anything else to divide $b + c$. This fails for prime, but work for any other composite, and we are done.

Here is a solution inspired by ISL 2005 N3. The answer is all composite $s$, which works by considering $a=1$, $b=m-1$, $c=n-1$, and $d=(m-1)(n-1)$ to obtain a construction for $x=mn$. Now we prove that all primes are impossible. Suppose that $a+b+c+d=p$ is a prime that divides $abc+bcd+cda+dab$. Then, in $\mathbb{F}_p$, there exists $s,t$ such that $$(x-a)(x-b)(x-c)(x-d) \equiv x^4+sx^2 + t \pmod p$$The RHS is even polynomial. Thus, $-a,-b,-c,-d$ are also a root. However, due to unique factorization in $\mathbb{F}_p$, we can permute $a,b,c,d$ so that $a\equiv -b\pmod p$ and $c\equiv -d\pmod p$. Thus, $p\mid a+b$, which is impossible due to size.

The answer is composite $s\geq 4$. By taking $(a,b,c,d)=(1,p-1,k-1,(p-1)(k-1))$, we see that $s=pk$ works for any $p,k\geq 1$. (Motivation: via small cases, note that $(a,b)=(1,d-1)$ always seems to lead to a solution for $d\mid s$.) We now show that prime $s=p$ don't work; henceforth take all congruences$\pmod p$. Then observe that \begin{align*} a+b+c+d&\mid abc+abd+acd+bcd \\ \implies a+b+c+d &\mid (a+b)(cd-(a+b)).\end{align*}$p\nmid a+b$ for size reasons, so $cd\equiv a+b$. Since $a+b\equiv -(c+d)$, this implies that $(c+1)(d+1)\equiv 1$. Now note that the expressions are symmetric, so we also have $(a+1)(b+1)\equiv 1$. Then \begin{align*} 1\equiv (a+1)(b+1)(c+1)(d+1) &= abcd + abc+abd+acd+bcd + ab+ac+ad+bc+bd+cd+1 \\ &\equiv abcd + 3(a+b+c+d) + 1 \\ &\equiv abcd+1 \end{align*}where second congruence comes from permuting $cd\equiv a+b$. Then $abcd\equiv 0$, so one of $a,b,c,d$ is divisible by $p=a+b+c+d$, which is absurd for size reasons. This is our desired contradiction.

Very cool result! We claim the answer is all composite $s$. Claim: all composite $s$ work. Let $a=n^2$, $b=k$, $c=n$, $d=kn$ for positive integers $n$ and $k$. We have $a+b+c+d=n^2+k+n+kn = (n+1)(n+k)$ which takes all composite values. and, $abc+abd+acd+bcd = n^3k+k^2n^3+n^4k+k^2n^2=n^2k(n+1)(n+k)$ which is divisible by $(n+1)(n+k)$. Claim: all prime $s$ doesn't work Lemma: Both $ab \equiv cd$ (mod $p$) and $a+b+c+d=p$ cannot hold. Assume for the sake of contradiction that $ab \equiv cd$ (mod $p$) and $a+b+c+d=p$ both hold. Clearly, $\gcd(a,p) = \gcd(b,p) = \gcd(c,p) = \gcd(d,p) = 1$. Thus, $d \equiv \frac{ab}{c}$ (mod $p$) So, $0 \equiv a+b+c+d \equiv a+b+c+\frac{ab}{c}$ (mod $p$) $\equiv \frac{c^2+ac+bc+ab}{c}$ $\equiv \frac{(a+c)(b+c)}{c} \equiv 0$ (mod $p$) Thus, $p|(a+c)(b+c)$. Since $p$ is prime, $p$ divides $a+c$ or $b+c$. This is a contradiction since $a+c$ and $b+c$ are less than $p$. Proving the claim. Now, assume $s$ is prime and assume $s$ divides $abc+abd+acd+bcd$. $abc+abd+acd+bcd \equiv 0$ (mod $a+b+c+d$) $abc+abd \equiv -cda-cdb$ $ab(c+d) \equiv cd(c+d)$ (mod $p$) Clearly $c+d<s$ so, $\gcd(c+d,s)=1$. Dividing on both sides yields $ab \equiv cd$ (mod $s$). And, by our lemma, $s = a+b+c+d \not = s$. Contradiction.

Until #11 you were all posting the SAME solution!!!

v_Enhance wrote: Determine all integers $s \ge 4$ for which there exist positive integers $a$, $b$, $c$, $d$ such that $s = a+b+c+d$ and $s$ divides $abc+abd+acd+bcd$. Proposed by Ankan Bhattacharya and Michael Ren Claim 1-: if $a+b+c+d|abc+abd+acd+bcd$ then $a+b+c+d=s$ is composite. Prove-: Assume that $s$ is prime We have $a+b+c+d|ab(c+d)+cd(a+b)\implies a+b+c+d|(a+b)(cd-ab)$ Now as $gcd(a+b, s)=1$ So $a+b+c+d|cd-ab--(*)$ similarly as $abc+abd+acd+bcd=ab(c+d)+cd(a+b)=ad(b+c)+(a+d)bc=(a+c)bd+(b+d)ac$ So we also have $a+b+c+d|bc-ad--(**),a+b+c+d|ac-bd--(***)$ Now $(*), (**),(***)\implies a+b+c+d|(b+d)(c-a), a+b+c+d|(c-d)(a+b), a+b+c+d|(a+d)(c-b)$ Now $s$ is prime so $s\nmid a+b, a+d, b+d$ But then this is only possible if $a=b=c=d$ Which is contradiction so $s$ is composite$\blacksquare$ Claim 2-: Every Composite $s$ is Possible. Prove-:So let $s=n\times m$ Now We can always choose $b, c$ such that $b+c=n$ and $a=(m-1)c, d=(m-1)b$ which obviously satisfies the condition $\blacksquare$

Amazing The answer is $s = \text{composite}$.

I finally got around to solving this great problem. The answer is all composite $s$. If $s$ is prime and $s\mid abc+abd+acd+bcd$, then: \begin{align*} 0&\equiv abc+abd+acd+bcd\\ &\equiv a(bc+bd+cd)+bcd\\ &\equiv bcd-(b+c+d)(bc+bd+cd)\\ &\equiv -(b^2c+bc^2+c^2d+cd^2+d^2b+db^2+2bcd)\\ &\equiv-(b+c)(c+d)(d+b)\pmod s\end{align*}Either $s\mid b+c$, $s\mid c+d$, or $s\mid d+b$, but since $s$ is greater than all of these, we have a contradiction. However, if $s$ is composite, we can write it as $s=xy$ for some $x,y>1$. Then choosing $(a,b,c,d)=(xy-x-y+1,x-1,y-1,1)$ gives $s\mid abc+abd+acd+bcd$.

We claim that all composites work. Work modulo $s$. In particular, let $d=-(a+b+c)$. Then we can factor $$abc+ab(-a-b-c)+ac(-a-b-c)+bc(-a-b-c) = -(a+b)(b+c)(c+a).$$If $s$ is prime, then one of $a+b, b+c, c+a$ must be a multiple of $s$. Yet they are all less than $a+b+c+d$, which is impossible. If $s$ is composite, then for the smallest divisor $k$ of $s$, let $a=1, b=k-1, c = \frac sk - 1$. Clearly the expression is a multiple of $s$, while $$1+k-1+\frac sk-1 = k+ \frac sk - 1 < s$$for all $k>1$. Thus such a tuple $(a, b, c, d)$ will always exist for $n$ composite as desired.

decided id attach overleaf cuz it looks better

The answer is all composite $s$. In general we should have $abc+abd+acd+bcd \equiv -(b+c+d)(bc+bd=cd)+bcd=-(b+c)(b+d)(c+d) \pmod{a+b+c+d}$, and if $s$ is prime this is clearly impossible. Otherwise if $s=xy$ where $x,y>1$ then take $(a,b,c,d)=(1,(x-1),(y-1),(x-1)(y-1))$, which works since $bc+bd+cd+bcd \equiv bcd+bc+bd+cd+b+c+d+1 \equiv (b+1)(c+1)(d+1) \pmod{s}$. $\blacksquare$

Notice the condition is equivalent to \[abc+abd+acd+bcd \equiv 0 \pmod{s}.\] Also, we can substitute $d=-a-b-c$ in and simplify to get \[(a+b)(b+c)(c+a) \equiv 0 \pmod{s}.\] Then, note that if $s$ is prime, this cannot be possible since each of $a+b, b+c, c+a$ are less than $s$. If $s$ is not prime, write it as $mn$. Then, $(a,b,c,d)=(1,m-1,n-1,(m-1)(n-1))$ works. The answer is $\boxed{\text{non-primes}}$.

The answer is when $s$ is composite. I will do the construction after I prove that prime $s$ don't work. Note that the given condition is equivalent to \[s\mid -abc-(ab+bc+ca)(-a-b-c)=\left(\sum_{\text{cyc}}a^2b\right)+2abc=(a+b)(b+c)(c+a).\]If $s$ is prime, then it must divide one of the three factors, say WLOG it divides $a+b$. But then $s\le a+b<a+b+c+d=s$, contradiction. Now we will show the construction for composite $s$. Let $s=mn$ be the representation of $s$ that is the product of two positive integers that are as close as possible with $m\le n$(for example, $35=5\cdot 7$ and $108=9\cdot 12$). Then have $b=m-1$, $a=1$, $c=n-b$, and $d=s-a-b-c$. The only hurdle here is that we need $s>a+b+c=m+n-1$, so we need $(m-1)(n-1)>0$, which is clearly true, so we are done. $\blacksquare$

Same as everyone... ISL 2005/N3 vibes! Solution: The answer is all composite $s \ge 4$. Take $(a,b,c,d) = (x,y,1,xy)$ for $x,y \ge 1$. This works since this gives $s = (1+x)(1+y)$ and suitable $x,y$ can be chosen to attain any composite $s$. For the other direction, we will manipulate the given expression mod $s$ into a pretty looking factored form. \begin{align*} X \coloneqq abc+abd+acd+bcd & = ab(c+d) + cd(a+b) \\ & \equiv -ab(a+b) + cd(a+b) \\ & \equiv (a+b)(cd-ab) \pmod{s} \end{align*}At this point, we will eliminate $d$ which looks the most alien term in the expression. We eliminate this by substituting $d \equiv -(a+b+c) \pmod{s}$. Simplification yields \[X \equiv -(a+b)(b+c)(c+a) \equiv 0 \pmod{s}.\]If $s$ is a prime, then $a+b+c+d \mid m$ for $m \in S \coloneqq \{a+b, b+c, c+a\}$. This is impossible since the $|s| > |m|$ for any $m \in S$. This concludes the solution. $\blacksquare$

We claim all composite $s$ work. \begin{align*} abc+abd+acd+bcd & \equiv abc+d(ab+ac+bc) \pmod{s} \\ &\equiv abc-(a+b+c)(ab+ac+bc) \pmod{s}\\ &\equiv -(a+b)(a+c)(b+c) \pmod{s} \end{align*}If $s$ is prime one of $(a+b)$, $(a+c)$, $(b+c)$, must be equal to $s$. However $a+b+c+d=s$, which is a contradiction. If $s$ is non-prime let $x$ denote the smallest positive divisor divisor of $s$ not equal to one we can use the construction $(a,b,c,d)=(x-1, 1, \tfrac{s}{x}-x+1, s-\tfrac{s}{x}-1)$ Which finishes the problem.

I claim that the answer is all composite $s$. First, we prove that prime $s$ do not work. Note that $s \mid (abc + bcd + acd + bcd)$, which implies that $s \mid ab(c + d) + cd(a + b)$, which implies that $s \mid ab(c + d) + cd(s - (c + d))$, which impies that $s \mid (ab - cd)(c + d)$. But, since $a + b + c + d$ is prime, we must thus have $a + b + c + d \mid (ab - cd)$. So, $a + b + c + d \mid (a^2 + ab + ac + ad - (ab - cd))$, so $a + b + c + d \mid (a + c)(a + d)$, which gives a contradiction, since $a + b + c + d$ is prime. If $s = a + b + c + d$ is composite, it may be factored into $s_1, s_2$ such that $s = s_1s_2$, and $s_1, s_2 > 1$. Then, we may choose $a = wx, b = yz, c = xy, d = zw$, where $x = 1, y = 1, z = s_2 - 1, w = s_1 - 1$, with $ab = cd$, and $a + b + c + d = (w + y)(x + z) = s_1s_2 = s$. \begin{remark} This choice was inspired by the so called ``Four Number Lemma". \end{remark}

Cute and easy problem

Very nice prob imo

The answer is all composite integers. To construct $s = xy$ for any integers $x \geq y > 1$, we can choose $(a,b,c,d) = (x,x,y-x,xy-x-y)$. If $s$ is prime, note that since $a+b+c+d \equiv 0 \pmod{p}$ and $abc + bcd + cda + dab \equiv 0 \pmod{p}$, we know that $a$, $b$, $c$ and $d$ are the roots of \[ Px^4 + Qx^2 + R\]modulo $p$, where $R$ is nonzero. In particular, if $r$ is a root of the above polynomial, $-r$ is also a root, but this is a contradiction since then $a+b+c+d \geq 2p$.

The answer is all composites $\ge 4$. For a construction take $(a, b, ka, kb)$, which clearly works; this gets $s = (k+1)(a+b)$ which can easily be turned into any composite. Suppose $s$ is prime. Mod $s$, \[ abc + (-a-b-c)(ab + bc + ca) \equiv 0 \pmod{s}. \]Let $a$, $b$, $c$ be the roots of a polynomial mod $s$. Particularly we have \begin{align*} x^3 - ux^2 + vx - uv &\equiv 0 \pmod{p} \\ x^2(x - u) + v(x - u) & \equiv 0 \pmod{p} \\ (x^2 + v)(x - u) & \equiv 0 \pmod{p}. \end{align*}Particularly the root of the quadratic factor is a size contradiction, since if $0 < a < p$ is a root of $x^2 + v$, then $p-a$ is the only other positive root smaller than $p$, contradiction.

We have that $a+b+c+d \mid abc+dab+dac+dbc$, $a+b+c+d \mid abc-(a+b+c)(ab+bc+cd)$, $a+b+c+d \mid (a+c)(a+b)(b+c)$. Thus we get that $a+b+c+d$ cannot be prime because of size reasons. Now suppose $a+b+c+d$ is composite and is equal to $mn$ where both $m$ and $n$ are not prime, than $(m-1)(n-1)+(m-1)+(n-1)+1$ works.

The answer is $s$ composite. Proof that these work: Let $a=wx$, $b=xy$, $c=yz$, and $d=zw$ for positive integers $w,x,y,z$. Then we have $$s=(w+y)(x+z).$$But notice that $$abc+abd+acd+bcd=wxyz(w+y)(x+z)\equiv0\pmod s.$$ Proof that primes don't work: We have $$(a+b)(a+c)(a+d)=(abc+abd+acd+bcd)+a^2(a+b+c+d)\equiv 0\pmod s,$$but then $s$ divides the product of numbers less than $s$, so $s$ cannot be prime.