3
$\begingroup$

I read somewhere that if $m$ is composite then $(m - 1)^{m - 1} \equiv m - 1 \pmod m$ and I was curious to try to prove it myself.
So I took as $m = 6$.
Now I can see that $5^5 \equiv 5 \pmod 6$

I was thinking along the following lines:
Since $\gcd(6,5) = 1$ this means that if we multiply $5$ with all the numbers from $1$ to $5$ we have to get all the numbers in different order.
I.e.
The numbers less than $6$: $1,2,3,4,5$.
Multiply the above by $5$: $5,4,3,2,1$ i.e. we get the same set of numbers but in different order.
Since: $1\cdot 2\cdot 3\cdot 4\cdot 5 = 5\cdot 4\cdot 3\cdot 2\cdot 1$ we also have:
$1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv (1\cdot 5) \cdot (2\cdot 5) \cdot (3\cdot 5) \cdot (4\cdot 5) \cdot (5\cdot 5) \Leftrightarrow 1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv 5^5 (1\cdot 2\cdot 3\cdot 4\cdot 5) \Leftrightarrow 1 \equiv 5^5$
Which is actually wrong.

What is the problem in my approach and thought process?

$\endgroup$
8
  • 2
    $\begingroup$ Seems to assume that $m$ is even, since the trailing term in the binomial expansion is $(-1)^{(m-1)}.$ $\endgroup$ Sep 18, 2021 at 15:52
  • $\begingroup$ The part where you are introducing the numbers less than $5$ doesn't make sense. What does that have to do with the title problem? Also, modulo $6$, that equivalence is correct, up until the final two elements, which should both be $0\mod 6$. $\endgroup$
    – abiessu
    Sep 18, 2021 at 15:54
  • 4
    $\begingroup$ Note: $(m-1)^{m-1} \equiv (-1)^{m-1} \pmod{m}$ therefore is $m$ is even we will get $(-1)^{m-1} = -1 \equiv m-1 \pmod{m}$. As @user2661923 said, this seems to only be true for even $m$ $\endgroup$
    – Igor
    Sep 18, 2021 at 15:55
  • $\begingroup$ @abiessu: I wasn't sure what title is best, so I gave it in the context of how it appeared $\endgroup$
    – Jim
    Sep 18, 2021 at 15:55
  • $\begingroup$ Your title is fine, except that you wrote $m - 1^{m-1}$ instead of $(m-1)^{m-1}.$ I think that the comment of @abiessu intends that he is confused (as am I) as to the relevance of your analysis starting with "...if we multiply $5$ with all the numbers from $1$ to $5$ ...". What analytical conclusion are you reaching for here? $\endgroup$ Sep 18, 2021 at 16:00

3 Answers 3

2
$\begingroup$

The fallacy in your argument is in the last step, where you "cancel" $1\cdot2\cdot3 \cdot 4\cdot 5$ from each side of the congruence.

As in ordinary arithmetic, you can only cancel factors that aren't $0$. (In fact, you can only reliably cancel factors that are relatively prime to the modulus.)

So in this case the assertion you are trying to prove is correct but your argument is not. The argument does work for arithmetic with a prime modulus.

$\endgroup$
4
  • 1
    $\begingroup$ No matter how big $m > 4$ is, $(m-1)! \equiv 0 \pmod{m}$ because that factorial will (usually) contain two numbers whose product is $m$. ("Usually" because you have to work a little harder when $m$ is the square of a prime.) $\endgroup$ Sep 18, 2021 at 16:21
  • $\begingroup$ I see. So if the product of the numbers $1.2.3..m-1$ when $m$ is composite has to be $0$ since the factors have to be there, isn't that condition sufficient to determine if a number $n$ is prime or not? Although may be not practical for huge $m$ $\endgroup$
    – Jim
    Sep 18, 2021 at 16:57
  • $\begingroup$ @Jim Yes, this is a terrible test for primality. Look up Wilson's Theorem. $\endgroup$ Sep 18, 2021 at 17:42
  • $\begingroup$ It is a test for primality but it is probably one of the must inefficient one can think of. The issue with determining primality is a matter of the difficulty of factoring. In figure out what $(m-1)!$ is we'd still have to determine and find those factors along with a lot more stuff. $\endgroup$
    – fleablood
    Sep 18, 2021 at 17:53
1
$\begingroup$

A most immediate thing to note is that $(m-1)\equiv -1 \pmod m$ always.

So $(m-1)^{m-1} \equiv (-1)^{m-1}\pmod m$. And $(-1)^{m-1} = -1$ if $m-1$ is odd and $(-1)^{m-1} = 1$ if $m-1$ is even. And as $-1 \equiv m-1\pmod m$ and $1\equiv m+ 1\pmod m$ we realize what you probably heard was

$(m-1)^{m-1} \equiv (-1)^{m-1} \equiv \begin {cases}1\equiv m+1 \pmod m& m\text{ is odd}\\-1\equiv m-1 \pmod m& m\text{ is even}\end{cases}$

"The numbers less than 6: 1,2,3,4,5. Multiply the above by 5: 5,4,3,2,1 i.e. we get the same set of numbers but in different order."

Note: That is because $5\equiv -1$ so $1,2,3,4,5$ times $5$ will be $-1,-2,-3,-4,-5$ which are $5,4,3,2,1$.

$1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv (1\cdot 5) \cdot (2\cdot 5) \cdot (3\cdot 5) \cdot (4\cdot 5) \cdot (5\cdot 5) \Leftrightarrow 1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv 5^5 (1\cdot 2\cdot 3\cdot 4\cdot 5) \Leftrightarrow 1 \equiv 5^5$ Which is actually wrong.

But $1\cdot 2\cdot 3\cdot 4\cdot 5\not \equiv 1$.

$1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv 0$.

And you od have $1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv (1\cdot 5) \cdot (2\cdot 5) \cdot (3\cdot 5) \cdot (4\cdot 5) \cdot (5\cdot 5) \Leftrightarrow 1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv 5^5 (1\cdot 2\cdot 3\cdot 4\cdot 5) \Leftrightarrow 0 \equiv 5^5\cdot 0$

Ah.... I see the issue...

Wilson's theorem: $(p-1)! \equiv -1 \pmod p$ !!!IF $p$ IS PRIME!!!

But if $m$ is composite that the theorem does not hold $(m-1)! \not \equiv 1 \pmod m$.

In fact:

If $m> 4$ is composite then $(m-1)! \equiv 0 \pmod m$.

Pf: If $m$ is composite then $m = dk$ for some $d,k$ which are neither $1$ nor $m$ and so are components of $(m-1)!$. So $m|(m-1)!$ if $m$ is composite and $(m-1)!\equiv 0 \pmod m$.

....unless!..... $m = p^2$ for some prime. Then $p$ only occurs as a component once. But then $p < 2p < .....< p^2$ and $p$ and $2p$ are components. In which case $p\cdot 2p = 2p^2 = 2m|(m-1)!$ and so $m|(m-1)!$ and $(m-1)! \equiv 0 \pmod m$.

....unless! .... $p=2$ and $m =2^2 = 4$. But in that case $(4-1)! = 6$ and $6\equiv 2\pmod 4$. That is the exception. But if $m > 4$ there is no exception.

=====

Oh.... You weren't doing Wilsons theorem... which would have been negative anyway....

You were assuming $ac \equiv bc \pmod m \implies a \equiv b\pmod m$.

No. Division is one of the operations you can't do via modular arithmetic (unless $m$ is prime).

If $ac \equiv bc \pmod m$ then $m|ac -bc=(a-b)c$. But that does not mean $m|a-b$ unless $\gcd(m,c) =1$. For example if we let $a= 5$ and $b=3$ and $c= 3$ and $m = 6$ we have $15 \equiv 9\pmod 6$ and $6|15-9 = (5-3)3 = 2\times 3$ but we do not have $6|2$. So we do not have $5\equiv 3 \pmod 6$.

So we can't do division. (Unless $m$ is prime)

$\endgroup$
4
  • $\begingroup$ When you say in the first paragraph: And as $-1 \equiv m+ 1\pmod m$ is that right? If $m=6$ then $m + 1 = 7 \equiv 1$. Why do you say $-1$? $\endgroup$
    – Jim
    Sep 19, 2021 at 10:00
  • $\begingroup$ I didn't say $-1 \equiv m\color{red} + 1 \pmod m$. I said $-1 \equiv m\color{red} - 1\pmod m$. If $m = 6$ then $m-1 = 5\equiv -1 \pmod m$. I said it, I meant it, and I stand by it. $\endgroup$
    – fleablood
    Sep 19, 2021 at 15:33
  • $\begingroup$ But I copy/pasted what I wrote from your 3rd sentence. That was a typo then? $\endgroup$
    – Jim
    Sep 19, 2021 at 22:35
  • $\begingroup$ Oh... there... yes, that is a typo. $\endgroup$
    – fleablood
    Sep 19, 2021 at 22:54
0
$\begingroup$

your statement $$1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv (1\cdot 5) \cdot (2\cdot 5) \cdot (3\cdot 5) \cdot (4\cdot 5) \cdot (5\cdot 5) \Leftrightarrow 1\cdot 2\cdot 3\cdot 4\cdot 5 \equiv 5^5 (1\cdot 2\cdot 3\cdot 4\cdot 5) \Leftrightarrow 1 \equiv 5^5$$

is not corrrect .

Note that $$1.2.3.4.5\equiv 0 \pmod 6 $$

$\endgroup$
8
  • $\begingroup$ I know it is not correct. My question is what is the fallacy in the steps? $\endgroup$
    – Jim
    Sep 18, 2021 at 16:09
  • $\begingroup$ $1.2.3.4.5\equiv 0 \pmod 6 \neq 1$ $\endgroup$ Sep 18, 2021 at 16:11
  • 1
    $\begingroup$ @Jim This analogizes to the following fallacious reasoning: $1 \times 0 = 2 \times 0$. Therefore $1 = 2.$ $\endgroup$ Sep 18, 2021 at 16:20
  • 1
    $\begingroup$ @Jim As a more critical example, $2 \times 3 \equiv 4 \times 3 \pmod{6}$. However, it is not the case that $2 \equiv 4 \pmod{6}.$ $\endgroup$ Sep 18, 2021 at 16:24
  • 1
    $\begingroup$ For future reference If you have $r\times t\equiv s\times t\pmod m$ you can divide both sides by $t$ IF you divide the $m$ by $\gcd(t,m)$. That is $r\times t\equiv s\times t\pmod m\implies r\equiv s \pmod {\frac {m}{\gcd(t,m)}}$. ... but that is a result for later.... this result would lead to $1*2*3*4*5\equiv 1*2*3*4*5*5^5\pmod 6\implies 1\equiv 5^5\pmod {\frac 6{\gcd(6,5!)}}\implies 1\equiv 5^5 \pmod 1$. Which is a trivial result as $1\equiv 0 \pmod 1$ and $5^5 \equiv 0 \pmod 1$ and EVERY integer $k \equiv 0 \pmod 1$. $\endgroup$
    – fleablood
    Sep 18, 2021 at 20:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .