How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
Why do we assume that $$(m,61) = 1\wedge (n,61) = 1 $$ ?
I mean why it is possible ?
Asked
Active
Viewed 129 times
3
-
1The gcd of any integer $n > 0$ and a prime $p$ is always 1. 61 is prime. – Vikram Saraph Aug 10 '14 at 22:56
-
@VikramSaraph: Not quite. For example, $7$ is prime, but $(7,14)$ is not $1$. – hmakholm left over Monica Aug 10 '14 at 22:58
-
Ah you're right, silly me, never mind. – Vikram Saraph Aug 10 '14 at 22:58
-
So what about my question ? – xawey Aug 10 '14 at 23:13
1 Answers
1
Here are the details of the proof. Suppose that $\,p\,$ is a prime such that $\,p\!-\!1\mid 60,\,$ so $\,\color{#c00}{(p\!-\!1)k = 60}.\,$ If $\,p\mid m\,$ or $\,p\mid n\,$ then $\,p\mid mn(m^{60}-n^{60}).\,$ Else $\,m,n\,$ are coprime to $\,p,\,$ so by little Fermat $\,{\rm mod}\ p\!:\ n^{\large\color{$c00}{60}} = (n^{\large \color{#c00}{p-1}})^{\large \color{#c00} k} \equiv 1^k \equiv 1.$ Similarly $\,m^{60}\equiv 1,\,$ so $\, mn(m^{60}-n^{60})\equiv mn(1-1)\equiv 0$. Therefore $\ p\mid mn(m^{60}\!-n^{60})\ $ for all primes $\,p\,$ such that $\,\color{#0a0}{p\!-\!1\mid 60}.$
However $\quad 56786730=2\times3\times5\times7\times13\times31\times 61 = \displaystyle\!\! \!\!\prod_{\large {\begin{array}\rm p\ {\rm prime}\\ \rm \color{#0a0}{p-1\mid\, 60}\end{array}}}\! p$
So, by the above, $\,mn(m^{60}\!-n^{60})$ is divisible by $\,2,3,5,7,13,31,61$ so also by their lcm = product.
Remark $\ $ Note that the proof for each prime $\,p\,$ splits into $2$ cases depending on whether or not $\,mn\,$ is coprime to $\,p.\,$ This case splitting is done so that we can apply little Fermat to the terms $\,m^{p-1}, n^{p-1},\,$ which requires $\,m,n\,$ coprime to $\,p\,$ (e.g. for $\,p=61,\,$ as in your question).
Bill Dubuque
- 272,048