AoPS Academy
![\[
\left| A_1 \cup A_2 \cup \dots \cup A_n \right| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n|
\]](http://latex.artofproblemsolving.com/5/f/8/5f8d35a9e8b235c072e7b97c500d37f3afb26a42.png)
![\[
\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right|
\]](http://latex.artofproblemsolving.com/f/c/0/fc0d752fbf3d6277e7f47c7ce01158fb91edce34.png)
) and M midpoint of BC. 
is the circumcircle of tringle 
and 
circumcircle of triangle 
. the line through C is tangent to at P and line through B is tangent to at Q. D is the midpoint of arc BC (does not contain A) in (
). prove that quadrilateral DPMQ is cyclic.
such that
by multiplying the conclusion we want by 
.![\[\sum_{i=0}^{p} \dbinom{p}{i} x^i \equiv x^p + 1 \pmod{p^2}\]](http://latex.artofproblemsolving.com/2/5/1/251b6cec157ca9b5df88377d0ec9172b61b76d99.png)
![\[ (1+x)^p \equiv x^p + 1 \pmod{p^2}\]](http://latex.artofproblemsolving.com/5/a/3/5a3369584e27ec4849c2c5450f3c79d27812d6fa.png)
then 
for 
. Then since that 
, we are done.
we have ![\[ \frac{1}{k} \equiv (-1)^{k-1} \frac{1}{p} \binom{p}{k} \pmod p. \]](http://latex.artofproblemsolving.com/6/2/e/62ee189bf1e3c26e996693c011cb1b563f8700ca.png)
Proof. Not too difficult. 
![\[ x - \frac {x^2}{2} + \frac {x^3}{3} - \cdots - \frac {x^{p - 1}}{p - 1} \equiv \frac{1}{p} \sum_{i=1}^{p-1} x^i \binom{p}{i} = \frac{1}{p} \left( (x+1)^p-x^p-1 \right). \]](http://latex.artofproblemsolving.com/2/5/c/25c2bb41de1bf45fa1b0cb07fa2365416dcf1d7a.png)
Note that the requirement 
but 
gives us 
, so 
which lets us transform the above into ![\[ \frac{1}{p} \left( (x+1)^p-x^p-1 \right) = - \frac{1}{p} \left( x^{2p}+x^p+1 \right) = - \frac{1}{p} \cdot \frac{x^{3p}-1}{x-1}. \]](http://latex.artofproblemsolving.com/d/5/b/d5b0b5b37f8ea33fc2e306e06bc63b92a2e5bc7b.png)
As , it now suffices to prove 
. For that use ![\[ x^{3p-1}-1 = \left(x^3-1 \right) \left(x^{3p-3}+x^{3p-6}+\dots+1 \right). \]](http://latex.artofproblemsolving.com/4/8/6/486d00b2aac9fcc771d4a41eea53765a413075c4.png)
The first factor is divisible by , so if we can show that the second factor is divisible by as well, then we are done. But using 
we get ![\[ x^{3p-3}+x^{3p-6}+\dots+1 \equiv \underbrace{1+1+\dots+1}_{p \text{ times}} = p \equiv 0 \pmod p. \]](http://latex.artofproblemsolving.com/1/2/4/1242e156e3b47c4c5d2aa26c7701fe45baec90c8.png)
Done. 
, we have 
Using Wilson's Theorem, and the above fact, it suffices to prove 
Since 
(which also gives 
, since 
is the order of 
modulo ), so we get that 
Let 
denote a complex cube root of unity. Then one easily gets (using the expansion of 
, and from 
, as well as by 
) that 
Thus, we find that 
where the last congruence follows by FLT, and the fact that 
implies 
. Hence, done. 
and 
. Then 
clearly divides 
but 
. However, what is the proof for this: then for then 
, which can be proven rather easy with some tricks involving Wilson's theorem, but for it is quite hard. then , it is enough to prove that if 
, then 
so as to discard the 
term. Remark that 
. Additionally remark that the condition implies there is an element of order in 
, , so 
. By the harmonic mod trick, the sum is![\[\tfrac 1p \sum_{k=1}^{p-1}x^k\binom{p}{k} = \tfrac 1p((1+x)^p-1-x^p).\]](http://latex.artofproblemsolving.com/d/1/3/d130231d11dd8eed8eb7c3e3c3da2ed55588d1da.png)
To show 
is divisible by 
, we show it is divisible by 
. Let 
. Compute that![\[(1+\omega)^p-1-\omega^p=(1+\omega)-1-\omega=0,\]](http://latex.artofproblemsolving.com/b/b/7/bb7695e0aec9701d5112ec5be67f42b8912ff032.png)
so 
. Compute that![\[p(1+\omega)^{p-1}-p\omega^{p-1}=p-p=0,\]](http://latex.artofproblemsolving.com/3/c/b/3cbfc43e6a0918c27145d2f6974a6b3bf8427dbf.png)
so 
. This implies the desired.
divides 
divides 
(by binomial theorem)
for some k ,expanding we just need to show that 
and by the well known lemma 
we get that 
,p)=1 .Now assume to the contrary that this is true and p>3 .Notice that either p-1 or p+1 is a multiple of 3.Note that Now just use powers over congruences and subtract the 2 results.We get a contradiction.Hence 
where we think of 
as a map from 
.
whenever has order .![\[f(z+1)=f(-z)\]](http://latex.artofproblemsolving.com/d/e/1/de137eeffb3879a15c828f8a7d3866ac90ee6f37.png)
and![\[f(z^2)=(1+z)f(z)+(1-z)f(-z).\]](http://latex.artofproblemsolving.com/7/0/a/70a78d74efaa6324f028d5206d57e770b8987624.png)
From there one can finish quickly: Note that 
and hence 
from the first functional equation.
and then again with 
we get![\[f(x)=(1+x^2)f(x^2)+(1-x^2)f(-x^2)=-xf(x^2)+(1-x^2)f(-x)=-x((1+x)f(x)+(1-x)f(-x))+(1-x^2)f(-x)=f(x)+(1-x)f(-x)\]](http://latex.artofproblemsolving.com/e/e/b/eebc5e23fde135953c8eafa1fc0c19b6a6736a59.png)
and hence 
and hence as desired.
, we have
Applying this, it suffices to show that
From but , we get , so by Exponent Lifting
so it suffices to prove that 
. Since 
, it follows that we only have to show . This is again by Exponent Lifting—we have
which yields the desired result. 
It suffices to show ![\begin{align*}\frac{(p-1)!}{p} \left[\binom{p}{1}x + \binom{p}{2}x^2 + \binom{p}{3}x^3 + \cdots + \binom{p}{p-1}x^{p-1}\right] \equiv 0 \pmod{p} \\ x - x^2 + x^3 + \cdots - x^{p-1} \equiv 0 \pmod{p}\end{align*}](http://latex.artofproblemsolving.com/a/a/7/aa703d5b24479f52c3f2891b445fd60799cdaf1c.png)
by the modfrac relation. So we know 
the second to last line coming from the fact that 
and 
which is why we can divide by and 
and the last line coming from the geometric formula. Hence by Euler totient function we know that ![\[\frac{1(1 - (x^2)^{(p-1)/2})}{1-x^2} \equiv \frac{1(1 - (x^{p-1}))}{1-x^2} \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/e/e/3/ee31d811576922268e0651c0240358566e06394b.png)
as desired.
term, and allow fractions mod .
Then, we have 
Thus, ti remains to show that 
which is also 
By binomial theorem, the LHS is 
, so it suffices to show that 
. Assume 
from now on.
but does not divide 
, we have 
Thus, 
, so it suffices to show that 
or 
Since the order of mod is 3, 
is not divisible by since we are assuming 
. Thus, it suffices to show that 
Rewrite as 
This is just LTE: 
so we are done.
and 
that 
., one concludes that it suffices to show that the sum 
is precisely 
modulo .
we have that 
, then 
, we have that as 
, so at present it suffices to show 
., and in particular, we obtain 
, and so it once more and finally suffices to show 
. However this is trivial, as 
, so that , as desired. 
trick, so that now we want to prove that divides![\[
\sum_{k=1}^{p-1} \binom pk x^k=(x+1)^p-x^p-1.
\]](http://latex.artofproblemsolving.com/1/8/a/18a10a865226826c92f997513c05eb10c77a7b55.png)
Since is a primitive cube root of unity, must be 
mod . Now use LTE to see that![\[
\nu_p\left((x+1)^p-(x+1-(x^2+x+1))^p\right)=\nu_p(x^2+x+1)+\nu_p(p)\ge 2,
\]](http://latex.artofproblemsolving.com/6/9/b/69b967d0e2c706a7804b6164d8e8419614de65d2.png)
where 
because . divides![\[
-x^{2p}-x^p-1.
\]](http://latex.artofproblemsolving.com/9/5/b/95b6280e4728872804e322b32e4899f6afed210b.png)
Noting that 
, it suffices to prove that divides 
. However, this is a direct application of LTE as 
, so we win. 
![\[ \sum_{i=1}^{p-1} \dfrac{(-1)^ix^i}{i} \equiv 0 \pmod{p}. \]](http://latex.artofproblemsolving.com/f/0/0/f0084586a58159747410d9945d579fdf1960e8cd.png)
.
is equivalent to proving 
.
. Now note that if we can show that 
, then we are done. By LTE, 
and we are done. 
Which is equivalent to
, we are going to prove that 
has 
as a double root, with this we finish as any polynomial that has 
as a root is divisible by 
; as 
then ; note that
(we used the fact that 
is a 6-th rooth of the unity) And we are done.
(mod ) and 
(mod ), we get that 
, so . Since is odd, this implies that 
. Now,
(mod ).
It thus suffices to show that 
By the Binomial Theorem, this reduces to 
Now, notice that by LTE 
so 
Hence, it suffices to show that 
Clearly, 
Meanwhile, by LTE, 
and thus the desired result follows. QED
![\[\sum_{n=1}^{p-1}\frac{p(-1)^{n-1}x^n}n\equiv0\pmod{p^2}.\]](http://latex.artofproblemsolving.com/c/f/7/cf71680e129b7414db09944b47df2afab0a79055.png)
Using the identity 
for all 
, it follows that ![\[\sum_{n=1}^{p-1}\frac{p(-1)^{n-1}x^n}n\equiv\sum_{n=1}^{p-1}\binom{p}nx^n\equiv(x+1)^p-x^p-1\pmod{p^2}.\]](http://latex.artofproblemsolving.com/e/f/1/ef10f555a7fc15a9493efb5ffaa6e56855cb941f.png)
and thus that , so now it suffices to show that divides the polynomial 
. But this follows from the fact that 
, where 
is a field therefore we can deal with rational numbers just fine. Hence our initial condition is equivalent to![\[
\left( x - \frac{x^2}{2} + \frac{x^3}{3} - \dots - \frac{x^{p-1}}{p-1} \right) \equiv 0 \mod p
\]](http://latex.artofproblemsolving.com/3/d/8/3d8783bbd1c755710b1bf43974e9cdb7d69aa406.png)
which is equivalent to![\[
\sum_{i=1}^{p-1} \dfrac{(-1)^i x^ i }{i} \equiv 0 \mod p
\]](http://latex.artofproblemsolving.com/e/f/8/ef8287c20e346f893d71e2ff275149df83654761.png)
Let 
be the polynomial 
.
but 
this implies 
. Now note that 
.
. As is an odd prime,we get 
. Hence 
for some natural 
.![\[
P(x) \equiv \left( \left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{3i+3} }{3i+3} \right) + \left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{3i+1} }{3i+1} \right) x + \left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{3i+2} }{3i+2} \right) x^2 \right) \mod p
\]](http://latex.artofproblemsolving.com/7/5/3/753772b1ad35e9e3adc77be233d02dc5e455e639.png)
Let 
.
. which will prove 
which will prove our original proposition . We will divide our proof into 2 parts , first we prove 
, in second part we will prove 
. 
, we get![\[
\left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{3i+3} }{(3i+3)} \right) \equiv \left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{3i+2} }{6m+1 -(3i+3)} \right) \mod p
\]](http://latex.artofproblemsolving.com/e/5/2/e52b799f7af602f8fa081fd1f0ff304844a740d2.png)
which implies![\[
A \equiv \left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{6m-2-3i} }{6m-2-3i} \right) \mod p
\]](http://latex.artofproblemsolving.com/2/0/7/207ed31e54c4f5278bcdee461012186805c884df.png)
as we know 
, we get![\[
A \equiv \left( \sum_{i=0}^{i=2m-1} \dfrac{(-1)^{3i+1} }{3i+1} \right) \equiv B \mod p
\]](http://latex.artofproblemsolving.com/3/c/a/3ca6557784fdc2782699d7cd02e77db16529af0c.png)
Proof that 
, which will automatically prove 
. First of all note that 
. As
(as each inverse is mapped bijectively to a non - zero element, therefore it is just sum of all non zero elements, sum of whose is 0).
which implies![\[
A+B+C \equiv \sum_{i=1}^{3m}\frac{1}{i} \mod p
\]](http://latex.artofproblemsolving.com/3/3/e/33e91342a633fda34db074caf098aabc4fe2a6c0.png)
Let 
. We claim that 
. To prove that , first notice (using and 
respectively),
, this implies
..
.
. This implies
, , as , we get . Since , we have 
,hence 
.![\[ p \mid (p - 1)!\left(x - \frac {x^2}{2} + \frac {x^3}{3} - \cdots - \frac {x^{p - 1}}{p - 1}\right).\]](http://latex.artofproblemsolving.com/1/a/3/1a36f070b56129d302daa3eb5d6dcb1851a90637.png)
John Berman
.
Thus, we want to show
To prove this, note that
Thus,
By Applying Lifting the Exponent Lemma
.
Now since 
,
,
.
.
,
![$[\mathbb{F}_p]$](http://latex.artofproblemsolving.com/a/3/a/a3a0a12ca383b225988d8c8641bd78e43a318038.png)
to 
to be the inverse of 
and so 
or 
,
,
Since 
,
,
,
,
,
.
.
and 
.
.
,
,
is a quadratic residue mod 
or 
,
since 
and 
be the primitive third roots of unity. Then, 
and 
are primitive sixth roots of unity. Therefore, 
.
,
.
.
,
.
,
,
.
