# 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: $\displaystyle 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 $\displaystyle p(x)$ is of degree $\displaystyle x^{p-2}$ and the RHS is a polynomial of the same degree that gives the same values for $\displaystyle x=1,2,...,p-1$

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

---

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