6
$\begingroup$

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 (remainder=1)$$ $$1\div 5=0(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$?"

$\endgroup$
  • 1
    $\begingroup$ This is true only in the case $x=2$. Why when you do $(-1) / 5$ the remainder is $1$ and not $-1$?. Anyhow, if $-1 \equiv 1 (mod x)$ it means that $x \mid -1-1=-2$ $\endgroup$ – user289143 Dec 13 '19 at 19:07
  • 3
    $\begingroup$ If you require remainders in $0\leq r<x$, then $-1$ leaves remainder $x-1$, while $1$ leaves remainder $1$, after division by $x$. In your example $-1=5\cdot (-1)+(5-1)$ and $1=5\cdot 0+1$ $\endgroup$ – egorovik Dec 13 '19 at 19:07
  • $\begingroup$ @user289143 Check this: quora.com/Can-the-remainder-be-a-negative-number-Why-or-why-not. $\endgroup$ – User123 Dec 13 '19 at 19:08
  • $\begingroup$ If you claim that dividing $-1$ by $5$ has a quotient of $0$ and a remainder of $1$, you are claiming that $5(0)+1$ is $-1$. Is it? $\endgroup$ – Arturo Magidin Dec 13 '19 at 19:14
8
$\begingroup$

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!)

$\endgroup$
4
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ Thank you, but I have already found an answer. The remainder of -1 equals n - 1. I thought it is 1. $\endgroup$ – User123 Dec 13 '19 at 20:15
  • 1
    $\begingroup$ @User123 But you didn't have a complete answer, e.g. no one else explained how we can use different remainder systems, etc. That's why I added this answer. $\endgroup$ – Bill Dubuque Dec 13 '19 at 20:17
  • $\begingroup$ Thank you! I haven't read to the end. I'm sorry. $\endgroup$ – User123 Dec 14 '19 at 18:28
  • 1
    $\begingroup$ @User123 Answers aren't only for the OP. It may help other readers who are interested enough to read it fully. $\endgroup$ – Bill Dubuque Dec 14 '19 at 18:30
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ -1 is congruent to 2 in modulo 3? That means, that 1 (1st remainder) = 2 (2nd remainder). Am I wrong? $\endgroup$ – User123 Dec 13 '19 at 19:20
  • 2
    $\begingroup$ @User123: You are wrong. You keep saying that when you divide $-1$ you get a remainder of $1$. That doesn’t happen. Saying “if you divide $a$ by $b$ the quotient is $q$ and the remainder is $r$” means, among other things, that $a=bq+r$. You say that dividing $-1$ by $3$ has quotient $0$ and remainder $1$, which means you are saying that $-1=3(0)+1$. Is that true? $\endgroup$ – Arturo Magidin Dec 13 '19 at 19:24
  • $\begingroup$ Then is the remainder equal -1? But -1 isn't equal to 2. $\endgroup$ – User123 Dec 13 '19 at 19:25
  • 1
    $\begingroup$ Is equal to 2, since $-1=(-1)\cdot 3 + 2$. We require the residue to be non-negative and to be less than $n$, in this case 3. $\endgroup$ – Julián Villaquirá Dec 13 '19 at 19:26
  • 1
    $\begingroup$ @User123: Remainders are usually defined to be nonnegative; the remainder when you divide $-1$ by $3$ is $2$. You kept saying it was $1$, and that is definitely wrong. $\endgroup$ – Arturo Magidin Dec 13 '19 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.