0

Picture:

I first thought I'd just have to do cases, i.e. if $m,n$ are even, $m=2l, n=2k$, where $k, l\in \Bbb Z$. But even in this case, alone, I wind up with $4kl(16l - 16k) = 64k(l^2) - 64l(k^2)\dots$ and that doesn't really get me anywhere.

Induction won't work, because I have no base case.

I feel as though this requires the use of mods, as being divisible by $30$ is tantamount to being equivalent to $0 \pmod {30}$, but where would I go from here?

Jose Arnaldo Bebita Dris
  • 1
John L.
  • 273
  • 1
    Working $\mod 30$ is tedious. Try to work $\mod 2, \mod 3$ and $\mod 5$ first and finally combine your results. – Tintarn Oct 01 '15 at 16:38
  • I'm really weak with mods. Could you explain to me how i'd go about that? Forgive my ignorance. I don't need you to do all of them, but if you could show me how to proceed using mod 5, i'd really appreciate that – John L. Oct 01 '15 at 16:40
  • Show the product is divisible by $2$, divisible by $3$, and divisible by $5$. Cases is OK, solve the problem first, then if you feel like it look for efficiencies. – André Nicolas Oct 01 '15 at 16:41
  • but in the case i described in the initial question, 64 is not divisisble by 5. – John L. Oct 01 '15 at 16:43
  • Induction can work. You only need to prove it for $m,n\geq 0$. Fix $n$. Then for $m=0,$ show it is true. Then if true for $(n,m)$, prove it is true for $(n,m+1)$. – Thomas Andrews Oct 01 '15 at 16:50

3 Answers3

2

HINT:

For prime $p,$ either $p|a$ or $(p,a)=1$

For the second case, $a^{p-1}\equiv1\pmod p$

If $p\nmid mn, m^{p-1}\equiv n^{p-1}\equiv1\pmod p\implies p\mid mn(m^{p-1}-n^{p-1})$

lab bhattacharjee
  • 274,582
  • This is surely the shortest way to prove it. Though, it does not seem that OP is familiar with Fermat's Little Theorem based on what he claims to know about modular arithmetic... – Tintarn Oct 01 '15 at 16:59
1

Alright, let's see how to do this.

First, it clearly suffices to prove that the term is always divisible by 2, 3 and 5 to prove that it's divisible by $30=2 \cdot 3 \cdot 5$.

So why is it divisible by 2?

Assume that it's not i.e. it's odd. Then clearly all factors must be odd. In particular, $m$ and $n$ must be odd. But then clearly $m^4-n^4$ is even. So we derived a contradiction i.e. the term is indeed even.

Let's go on to a more difficult part: Why is it divisible by 3?

Assume that it's not. Then none of the factors can be divisible by 3.

In particular, $m$ and $n$ must not be divisible by 3. Also $m^4-n^4=(m^2+n^2)(m+n)(m-n)$ (it's really useful to know this factorization!) must not be divisible by 3.

But if $m,n$ are both not divisible by 3 then they either have the same remainder $\mod 3$ in which case $m-n$ is divisible by 3 or one of them is $1 \mod 3$ and the other $2 \mod 3$ in which case $m+n$ is divisible by 3. You see, in either case we derived a contradiction. Hence the term is indeed divisible by 3.

Now, we are left to prove that it's divisible by 5. This is surely the hardest part of the problem but maybe you can now think of a way to prove this on your own?

Tintarn
  • 2,931
  • Thank you so much for helping me with this! I seriously appreciate it.

    however, as I am very, VERY weak with mods, perhaps you could absolve me of a few confusions:

    firstly, why is m^4 - n^4 even if both m and n are odd? surely I could just substitute 2k+1 for m, and 2l+1 for n, and foil it out, but this seems tedious. Is there a theoretical reasoning for this that i'm just not seeing?

    I was going to ask about the latter half of your argument, but it just clicked!

    Thank you SO much. Besides the one confusion listed above, I'll try my luck with mod 5! :)

     – John L. Oct 01 '15 at 16:54
  • @JohnL.: You are welcome. Just ask the precise question which is bothering you. – Tintarn Oct 01 '15 at 16:56
  • Ahh i got it with mod 5 after! Thank you SO much!! – John L. Oct 01 '15 at 17:04
  • @JohnL. , an odd to the fourth is odd (2 doesn't divide it still), and the difference of two odds is even. – Calvin Khor Oct 01 '15 at 17:06
  • @CalvinKhor thank you so much! – John L. Oct 01 '15 at 17:18
1

Induction can work. First, note that you only need to prove for $m,n\geq 0$, since:

$$30\mid mn(m^4-n^4)\iff 30\mid |m|\cdot|n|\left(|m|^4-|n|^4\right)$$

Now, it is true for $(0,n)$.

If true for $(m,n)$ then $$\begin{align} (m+1)n((m+1)^4-n^4) &= (m+1)^5n - n^5(m+1)\\ &=(m^5n-n^5m) + (5m^4+10m^3+10m^2+5m+1)n-n^5\\ &=(m^5n-n^5m) + 5mn(m^3+2m^2+2m+1)-(n^5-n) \end{align}$$

So you need to prove that $30\mid n^5-n$ and $6\mid m(m^3+2m^2+2m+1)=m(m+1)(m^2+m+1)$.

These you can prove as lemmas by induction on the one variable.

Not a pretty answer, but you can do induction on this sort of question.

Thomas Andrews
  • 177,126
  • ahh see, my induction is not that strong yet!

    thank you for showing me it was possible, though! I really appreciate it--I want to learn all that I can!!

     – John L. Oct 01 '15 at 17:05