<s>[INST] Error in my approach to prove that $(m-1)^{m-1} \equiv m - 1 \pmod m$ using a concrete example 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?
 [/INST] 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)
</s>