# Thread: two problems dealing with congruences

1. ## two problems dealing with congruences

1. let p be a prime number. Show that (p - 1)! is congruent to (-1)mod p

2. prove criteria for divisibility by 2, 3, 4, 5, 9, 10, 11 using congruences modulo appropriate powers of 10

for this one, I have proved 2 and 10 modulo 10, but am stuck on 3

for divisibility by 3:

say n = d0 + 10d1 + ... +(10^k)dk

so I need to prove that if d0 + d1 + ... +dk is divisible by 3, then so is n

I can see how it would work modulo 3 (start with d0 +d1 +... +dk is congruent to 0 mod 3 and manipulate it to get n is congruent to 0 mod 3), but the problem clearly states i need to use modulo appropriate powers of 10... a starting point on this would be great. Thanks!

2. 1. Note that: $
p\left( x \right) = x^{p - 1} - \left( {x - 1} \right) \cdot ... \cdot \left( {x - p + 1} \right) = \sum\limits_{k = 1}^{p - 1} {k^{p - 1} \cdot \tfrac{{\left( {x - 1} \right) \cdot ...\left( {x - k + 1} \right) \cdot \left( {x - k - 1} \right)... \cdot \left( {x - p + 1} \right)}}
{{\left( {k - 1} \right) \cdot ...\left( {k - k + 1} \right) \cdot \left( {k - k - 1} \right)... \cdot \left( {k - p + 1} \right)}}}
$

Since $p(x)$ is of degree $x^{p-2}$ and the RHS is a polynomial of the same degree that gives the same values for $x=1,2,...,p-1$

Thus: $
p\left( 0 \right) = - \left( {p - 1} \right)! = \sum\limits_{k = 1}^{p - 1} {k^{p - 1} \cdot \tfrac{{\left( {0 - 1} \right) \cdot ...\left( {0 - k + 1} \right) \cdot \left( {0 - k - 1} \right)... \cdot \left( {0 - p + 1} \right)}}
{{\left( {k - 1} \right) \cdot ...\left( {k - k + 1} \right) \cdot \left( {k - k - 1} \right)... \cdot \left( {k - p + 1} \right)}}}
$

Simplifying we get: $
\left( {p - 1} \right)! = \sum\limits_{k = 1}^{p - 1} {\binom{p-1}{k} \cdot k^{p - 1} \cdot \left( { - 1} \right)^{p - 1 - k} }
$

Now by Fermat's Little Theorem and the Binomial Theorem: $\sum\limits_{k = 1}^{p - 1} {\binom{p-1}{k} \cdot k^{p - 1} \cdot \left( { - 1} \right)^{p - 1 - k} } \equiv{\sum\limits_{k = 1}^{p - 1} {\binom{p-1}{k} \cdot \left( { - 1} \right)^{p - 1 - k} }}=(-1)^p (\bmod.p)$

And the result follows.

For more proofs see here

3. Originally Posted by minivan15
for divisibility by 3:

say n = d0 + 10d1 + ... +(10^k)dk

so I need to prove that if d0 + d1 + ... +dk is divisible by 3, then so is n

I can see how it would work modulo 3 (start with d0 +d1 +... +dk is congruent to 0 mod 3 and manipulate it to get n is congruent to 0 mod 3), but the problem clearly states i need to use modulo appropriate powers of 10... a starting point on this would be great. Thanks!
Notice that 10 is congruent to 1 (mod 3), and therefore so is any power of 10. Thus d0 + 10d1 + ... +(10^k)dk is congruent to ...

4. okay i see how that would go..thank you

I think I may have misunderstood the problem...does the phrase "modulo appropriate powers of 10" refer to doing 10 mod something (i.e. 10 congruent to 1 mod 10)? Because I thought it meant doing something mod 10 (i.e. d0 congruent to n mod 10)

if someone could clear that up that would be great. Thank you for your answers!

5. Originally Posted by minivan15
okay i see how that would go..thank you

I think I may have misunderstood the problem...does the phrase "modulo appropriate powers of 10" refer to doing 10 mod something (i.e. 10 congruent to 1 mod 10)? Because I thought it meant doing something mod 10 (i.e. d0 congruent to n mod 10)

if someone could clear that up that would be great. Thank you for your answers!
I see what you mean. I hadn't noticed the strange way that the question is phrased. I think that it must surely have meant to say "using powers of 10 reduced by an appropriate modulus." I don't see that you can get anywhere by using a power of 10 as the modulus.

6. Originally Posted by minivan15
1. let p be a prime number. Show that (p - 1)! is congruent to (-1)mod p
Kinda similar to what PaulRS said.

Consider $f(x) = x(x-1)...(x-(p-1))$ over $\mathbb{Z}_p$, $p$ odd.
Notice that $f(0) = f(1) = ... = f(p-1) = 0$.
Consider $g(x) = x^p - x$.
Notice that $g(0) = g(1) = ... = g(p-1) = 0$.
The polynomial $f(x) - g(x)$ has degree $p-1$ and it is $0$ for $p$ values.
This must be that $f(x) - g(x)$ is the zero polynomial and so $f(x) = g(x)$.
The $x$ coefficient of $f(x)$ is $(-1)^{p-1}(1)(2)...(p-1) = (p-1)!$.
The $x$ coefficient of $g(x)$ is $-1$.
Therefore, $(p-1)! \equiv -1(\bmod p)$.

---

Here is another proof, again $p>2$.
Let $0 < x < p$, if $x$ is its own inverse mod $p$ then $x^2 \equiv 1(\bmod p)$.
Thus, $(x-1)(x+1) \equiv 0(\bmod p) \implies x = 1 \text{ or }p-1$.
If $1 < x < p-1$ then there is $1 < y < p-1$ so that $xy\equiv 1(\bmod p)$ and $x\not = y$.
In the list $2,3,...,p-2$ for every $a\in \{2,...p-2\}$ pair it with $b$ so that $ab\equiv 1(\bmod p)$.
Therefore, $(p-1)!\equiv (p-1) \equiv -1(\bmod p)$ because we can rearrange the factors to produce $1$ mod $p$.
(We do not pair $1$ or $p-1$ because they only pair with themselves).