5

How can I prove that $30 \mid ab(a^2+b^2)(a^2-b^2)$ without using $a,b$ congruent modulo $5$ and then $a,b$ congruent modulo $6$ (for example) to show respectively that $5 \mid ab(a^2+b^2)(a^2-b^2)$ and $6 \mid ab(a^2+b^2)(a^2-b^2)$?

Indeed this method implies studying numerous congruences and is quite long.

Chon
  • 6,002
  • As noted in the answers below this question is more a test of understanding than it seems, as it invites you to use mathematical knowledge to reduce the numbers of cases you need to consider. – Mark Bennet Jul 23 '11 at 09:22

5 Answers5

7

Hint: First write $f(a,b)=ab(a^2+b^2)(a^2-b^2)=a^5b-b^5a$. Recall Fermat's Little Theorem which states $x^{p-1}\equiv 1 \pmod{p}$ for $x$ not divisible by $p$.

Assume $5$ does not divide either of $a,b$. (otherwise it follows automatically that $5|f(a,b)$) Then $$a^5b-b^5a\equiv ab-ba\equiv 0\pmod{5}$$ and we see that $5|f(a,b)$.

You can prove that $2$ and $3$ divide $f(a,b)$ in the same way.

(An alternative way to see that it is divisible by $2$ is to note that one of $a$, $b$, $a^2+b^2$ must be divisible by $2$)

Eric Naslund
  • 72,099
7

You need to show $ab(a^2 - b^2)(a^2 + b^2)$ is a multiple of 2,3, and 5 for all $a$ and $b$.

For 2: If neither $a$ nor $b$ are even, they are both odd and $a^2 \equiv b^2 \equiv 1 \pmod 2$, so that 2 divides $a^2 - b^2$.

For 3: If neither $a$ nor $b$ are a multiple of 3, then $a^2 \equiv b^2 \equiv 1 \pmod 3$, so 3 divides $a^2 - b^2$ similar to above.

For 5: If neither $a$ nor $b$ are a multiple of 5, then either $a^2 \equiv 1 \pmod 5$ or $a^2 \equiv -1 \pmod 5$. The same holds for $b$. If $a^2 \equiv b^2 \pmod 5$ then 5 divides $a^2 - b^2$, while if $a^2 \equiv -b^2 \pmod 5$ then 5 divides $a^2 + b^2$.

This does break into cases, but as you can see it's not too bad to do it systematically like this.

Zarrax
  • 44,950
3

The intention of this answer is to show you that trying all possibilities is in fact not that long. (Of course, it si more elegant, when you find a solution which avoids trying all possibilities.) Let me start by plotting 5x5 table with all possibilites for the remainders of a and b. (I do not know of a good way of making tables here - I tried something anyway.)

$$ \begin{array}{c|ccccc} b \backslash a & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & & & & & \\ 1 & & & & & \\ 2 & & & & & \\ 3 & & & & & \\ 4 & & & & & \\ \end{array} $$

If we rewrite our expression as $ab(a-b)(a+b)(a^2+b^2)$, we see that all possibilities where $a=0$ or $b=0$ are ok (marked by $\circ$).

$$ \begin{array}{c|ccccc} b \backslash a & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & \circ & \circ & \circ & \circ & \circ \\ 1 & \circ & & & & \\ 2 & \circ & & & & \\ 3 & \circ & & & & \\ 4 & \circ & & & & \\ \end{array} $$

Also possibilities where a=b are ok (since $a-b\equiv 0\pmod 5$ and so are those where $a=5-b$ (since $a+b\equiv 0\pmod 5$), hence we can omit both diagonals (marked by $\bullet$).

$$ \begin{array}{c|ccccc} b \backslash a & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & \circ & \circ & \circ & \circ & \circ \\ 1 & \circ & \bullet & & & \bullet \\ 2 & \circ & & \bullet & \bullet & \\ 3 & \circ & & \bullet & \bullet & \\ 4 & \circ & \bullet & & & \bullet \\ \end{array} $$

There are only 8 possibilities left, and since the roles of a and b are symmetric, we only have to try: (1,2), (1,3), (4,2), (4,3). In all these cases $a^2+b^2\equiv 0 \pmod 5$.

2

Below I show it is a very special case of following generalization of the Euler-Fermat theorem.

Theorem $\ $ Suppose that $\rm\ n\in \mathbb N\ $ has the prime factorization $\rm\:n = p_1^{e_{\:1}}\cdots\:p_k^{e_k}\ $ and suppose that for all $\rm\,i,\,$ $\rm\ e\ge e_i\ $ and $\rm\ \phi(p_i^{e_{\:i}})\mid f.\ $ Then $\rm\ n\mid (ab)^e\,(a^f-b^f)\ $ for all $\rm\: a,b\in \mathbb Z.$

Proof $\ $ Notice that if $\rm\ p_i\mid ab\ $ then $\rm\:p_i^{e_{\:i}}\ |\ (ab)^e\ $ by $\rm\ e_i \le e.\: $ Else $\rm\:a\:$ and $\rm\:b\:$ are coprime to $\rm\: p_i\:$ so by Euler's phi theorem, $\rm\ mod\ q = p_i^{e_{\:i}}\!: \ a^{\phi(q)}\equiv 1\equiv b^{\phi(q)} \Rightarrow\ a^f\equiv 1\equiv b^f\: $ by $\rm\: \phi(q)\mid f.\ $ Thus since all $\rm\ p_i^{e_{\:i}}\ |\ (ab)^e\ (a^f - b^f\:)\ $ so too does their lcm = product = $\rm\: n.$

Corollary $\rm\ \ 6p\mid a\: b^p - b\: a^p\ $ for all $\rm\:a,b\in \mathbb Z,\:$ prime $\rm\:p\ne 2,3$

Specializing $\rm\ p = 5\ $ yields the result sought in the question.

Remark $\: $ Note that the proof of the general theorem is less work than some other direct proofs of your special case. For some other variations (e.g. Carmichael's) see my posts here.

Bill Dubuque
  • 272,048
1

Hint for the divisors 2 and 3.

Note the factorisation $ab(a+b)(a-b)(a^2+b^2)$ which is divisible by $ab(a-b)(a+b)$ Either one of $a,b$ is divisible by 2 (or 3) or not. If not, look at the other factors to complete the proof.

Studying cases does not look too onerous to me.

Mark Bennet
  • 100,194