Isn't 1 congruent to -1?

Question

I have read something about Wilson's theorem, but I found that $$(n-1)!\ \equiv\ -1 \pmod n$$ I thought, that $-1\equiv 1\pmod x$, but in all literature, I only found upper theorem.

My reason why I am asking this is that $-1$ gives the same remainder as $1$ when dividing with some number. (Remainder can't be negative.)

Example: $$-1\div5=0 \text{ (remainder = 1)}$$ $$1\div 5=0\text{ (remainder = 1)}$$

Question: Is it true, that $-1\equiv 1 \pmod x$?

Thank you in advance!

P.S.

We can rewrite the title of the question into "Why is true $(n-1)!\ \equiv\ -1 \pmod n$ and not $(n-1)!\ \equiv\ 1 \pmod n$?"

Answer 1

The only $x$s for which $1$ and $-1$ are congruent are $1$, $-1$, $2$, and $-2$.

There are two standard ways of defining the congruence. The most common one you do not seem to be using:

Definition. Let $n$ be an integer. We say that integers $a$ and $b$ are congruent modulo $n$, written $a\equiv b\pmod{n}$, if and only if $n$ divides $a-b$.

Here you see that $-1\equiv 1\pmod{x}$ holds if and only if $x$ divides $-2$, which is only possible if $x=\pm 1$ or $x=\pm 2$.

Alternatively, one uses division with remainder.

Division algorithm. Let $b$ be a nonzero integer, and let $a$ be any integer. Then there exist unique integers $q$ and $r$ such that $a=bq+r$, and $0\leq r \lt |b|$. If $q$ and $r$ are such integers, $q$ is called the quotient of dividing $a$ by $b$, and $r$ is the remainder when dividing $a$ by $b$.

With those definitions, we have the following theorem, which may also be used as a definition of congruence modulo nonzero $n$:

Theorem. Let $n$ be a nonzero integer. Then $a$ and $b$ are congruent modulo $n$ if and only if $a$ and $b$ have the same remainder when divided by $n$.

Proof. Write $a=q_1n+r_1$, $b=q_2n+r_2$, with $0\leq r_1\lt |n|$, and $0\leq r_2\lt |n|$. Without loss of generality, say $r_1\geq r_2$. Then $a-b = (q_1-q_2)n+(r_1-r_2)$, and $0\leq r_1-r_2\leq r_1\lt |n|$, so the remainder when dividing $a-b$ by $n$ is $r_1-r_2$.

Thus, $a\equiv b\pmod{n}$ if and only if $n$ divides $a-b$, if and only if $r_1-r_2=0$, if and only if $r_1=r_2$, if and only if the remainders when dividing $a$ by $n$ and when dividing $b$ by $n$ are equal. $\Box$

The problem is that you have to be careful with negative numbers: if you divide $-1$ by $3$, the quotient is not $0$: the quotient is $-1$ with a remainder of $2$, since $-1=(-1)3 + 2$. If you divide $-1$ by $5$, the quotient is $-1$ with remainder $4$.

(And in any case if you divide $-1$ by $5$, it is certainly not true that the quotient is $0$ and the remainder is $1$, because that would mean that $-1 = 0(5)+1$, which is certainly false!)

Answer 2

No, in general this is false. Take $n=3$. Then $-1\equiv_3 2\not\equiv_3 1$. Just think of $-1$ not as a negative number but as $n-1$.

Answer 3

$a\div b\,$ has remainder $\,r\,$ means $\,a = q\,b + r\,$ for some quotient $q\in\Bbb Z,\,$ where the remainder $\,r\,$ is normalized to be unique by some convention, i.e. $\,r\,$ must lie in a fixed complete set of remainders - usually the set $\,\color{#0a0}{0\le r< b},\,$ but another common choice is least magnitude reps, e.g. the remainders $\,\color{#c00}{0,\pm1,\pm2}\pmod{\!5}.\,$ In the latter case we do have negative remainders, e.g. in your mentioned case we have $\,a\div 5\,$ has remainder $\,-1\iff a = 5\,q - 1,\,$ e.g.

$$\begin{align} -6 &\,=\, 5(-1)-\!1\\ \color{#c00}{-1} &\,=\, 5\cdot 0\ -\ 1\\ \color{#0a0}4 &\,=\, 5\cdot 1\ -\ 1\\ 9 &\,=\, 5\cdot 2\ -\ 1\end{align}\qquad $$

So $\,-6,-1,4,9\,$ have remainder $\,\color{#c00}{-1}\,$ using least magnitude reps vs. remainder $\,\color{#0a0}4\,$ with usual reps.

As for $\, -1\div b\,$ having remainder $\,1,\,$ it means $\,\exists\, q\!:\, {-}1 = q\,b + 1\! \iff\! \exists\,q\!:\ q\,b = -2\!\iff\! b\mid 2,\,$ hence it is true iff the divisor $\, b = \pm2\,$ or $\,\pm1,\,$ and $\,1\,$ lies in our chosen normal set of remainders.

That said, it is usually more convenient to work with congruences rather than normalized remainders since congruences are more compatible with arithmetic (see Congruence Rules) and they give us the flexibility to vary the choice of remainder rep as we like - choosing what is most convenient in any context. For example when casting out elevens it is more convenient to choose the rep $-1\,$ from the congruence class $\,10+11\Bbb Z\,$ when computing $10^n\equiv (-1)^n\pmod{\!11}$. This is analogous to having the flexibility to work with fractions that are not normalized (i.e. not reduced to lowest terms), e.g. the fraction addition rule is stated most simply by scaling them to have a common denominator (which generally yields non-reduced fractions). It would be very inconvenient if we always had to work with reduced fractions - just like it is inconvenient to compute $10^n$ vs. $(-1)^n$ when casting out elevens.