Let $a, b, c, d, e$ be distinct positive integers such that $a^4 + b^4 = c^4 + d^4 = e^5$. Show that $ac + bd$ is a composite number.
[Math] On $a^4 + b^4 = c^4 + d^4 = e^5$.
contest-mathelementary-number-theorynumber theory
Related Solutions
Let $p$ be a prime. Henceforth, work modulo $p$. Consider $ P = \{ s \pmod{p} | s \in S \}$.
Hint: Show that $P$ is either a singleton, or the entire residue class.
Looking at $P$ is very natural, and the result is reasonably easy to guess by looking at small cases of $p$.
EG For $ p = 7$, try the cases where we have seeds $\{1\}, \{2\}, \{3\}$ and see what you get. These cases are somewhat distinct, have a lot to offer, and might suggest ways to prove the hint.
This takes some work. If you're stuck, show what you've tried.
If $ 0 \in P$, then $ 1 \in P$ and by induction $P = \{ 0, 1, \ldots, p-1 \}$.
Suppose we have distinct non-zero elements $s_1, s_2 \in P$. Consider the map $P \rightarrow P$ with $ s \rightarrow s_1 s + 1 $.
Verify that the map is a bijection.
Hence, conclude that $\sum s_i \equiv s_ 1 ( \sum s_i) + |P|$
If $ \sum s_i \equiv 0$, then $|P| = p$ as desired.
Otherwise, if $ S = \sum s_i \not \equiv 0$, conclude that $ s_1 \equiv 1 - \frac{|P|}{S} \equiv s_2 $, which is a contradiction.
Corollary: For any $ a \in S$, given any prime $p$ that doesn't divide $ a^2 - a + 1 $, then $ a^2 + 1 \not \equiv a \pmod{p}$, so $P$ has at least 2 elements thus is the entire residue class, and thus there exists some element of $S$ that is a multiple of $p$.
Hence, the set of primes that does not divide any element of $S$, is a subset of the prime factors of $a^2 - a + 1$ (and thus is finite).
Notes:
- With the seed $ a = 1$, we get $ S = \mathbb{N}$. This isn't that useful, but it does suggest the "entire residue class".
- With the seed $ a = 2$, we get a subset of $ \{ 3k+2 \}$, and we see that $ 3 = a^2 -a + 1$ is the only prime that doesn't divide any term of this larger set.
- If $ 1 \in P$, we can likewise show that by induction that $2, 3, \ldots p-1, 0 \in P$. Also, the map $ s\rightarrow 1\times s + 1 $ gives us the result.
- Clearly the only way to show $ ab+1 = 1 \in P$ is that there exists an $ab \equiv 0 \in P$, which then requires an $ a\equiv 0 \in P$.
- By using $ ab + 1 = 0 \in P$, this opens us a lot of possibilities. In particular, if $ |P| > p/2$, then we can conclude $ 0 \in P$ and hence the result.
- I'd love to see a solution along these lines.
- Some sequences to naturally consider are:
- $a_{i+1} = a_i ^2 + 1, a_ 1 = a $
- $ b_{i+1} = a \times b_i + 1, b_ 1 = a$.
- $c_{i+2} = c_{i+1} \times c_i + 1 , c_1 = c_2 = a$.
- I'm interested in any solution using this, but TBH I doubt a solution exists (some details below).
- For $ p = 7$, starting with seed $2$,
- if you use the sequence $a_i$, you get $ 2, 5 , 5, 5, \ldots$ so are stuck. It is when you use $ 2 \times 5 + 1 \equiv 4$ that breaks you out.
- If you use the sequence $b_i$, then you get $2, 5, 4, 2, 5, 4, \ldots$ and are stuck, so we need $ 5\times 4 + 1 \equiv 0$.
- If you use $c_i$, then you'd get $2, 2, 5, 4, 0, 1, 1, 2, 3, 0, 1, 1, 2, 3, \ldots $ and are stuck (no 6).
- This explains why I doubt there exists a solution via considering $a_i$ / $b_i$ / $c_i$ only.
- The singleton case arises when we have $ a^2 + 1 \equiv a $ EG $a=2, p = 3$, or $ a = 3, p = 7$.
Best Answer
Assume that $p=ac+bd$ is prime. Without loss of generality, we may assume that $a>c,d$ from which follows that $b<c,d$. Also, $a,b,c,d<p$, and so must all be relatively prime with $p$.
Computing modulo $p$, we have $ac \equiv -bd$ which leads to $(ac)^4\equiv(bd)^4$. Exploiting $a^4+b^4=c^4+d^4$ we get $$ (a^4+b^4)c^4=(ac)^4+(bc)^4\equiv(db)^4+(bc)^4=(c^4+d^4)b^4=(a^4+b^4)b^4 $$ which means that either $p$ divides $a^4+b^4=c^4+d^4$, or $b^4\equiv c^4$.
We can exclude the alternative $p|a^4+b^4$ since that would make $p|e$, which in turn would require $e\ge p=ac+bd>a+b$ which leads to $e^5>a^4+b^4$. Note that this is the only use for the equality with $e^5$.
So now we know that $b^4\equiv c^4$, which means that $$ p|c^4-b^4=(c^2+b^2)(c+b)(c-b). $$ Again, $p>c+b$, so we must have $p|c^2+b^2$. However, $c^2+b^2<ac+bd=p$ as $c<a$ and $b<d$, which makes $p|c^2+b^2$ impossible.
Thus, no such $a,b,c,d$ exist for which $p$ is prime.
This was written late at night, so I hope I didn't make any glaring mistakes.