1. Note that:
Since is of degree and the RHS is a polynomial of the same degree that gives the same values for
Thus:
Simplifying we get:
Now by Fermat's Little Theorem and the Binomial Theorem:
And the result follows.
For more proofs see here
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!
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!
Kinda similar to what PaulRS said.
Consider over , odd.
Notice that .
Consider .
Notice that .
The polynomial has degree and it is for values.
This must be that is the zero polynomial and so .
The coefficient of is .
The coefficient of is .
Therefore, .
---
Here is another proof, again .
Let , if is its own inverse mod then .
Thus, .
If then there is so that and .
In the list for every pair it with so that .
Therefore, because we can rearrange the factors to produce mod .
(We do not pair or because they only pair with themselves).