0
$\begingroup$

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, $x\mid y$ means $x$ divides $y$.

  1. $p\mid{p\choose k}$
  2. $(ap + 1)^p \equiv 1\pmod{p^2}$
  3. $a^{p(p−1)} \equiv 1\pmod{p^2}$
  4. $p \mid a^p − a$.
  5. Prove that for every integer numbers $a$ and $b$, and every prime number $p$:
    $p\mid(a + b)^p − a^p − b^p$.

However, we are not allowed to use Fermat's Little theorem or Euler's totient theorem. Any guidance on how to go about and solve this problem would be greatly appreciated. Thank you!

$\endgroup$
4
  • $\begingroup$ You need $a$ to be coprime to $p$ for at least #3. $\endgroup$
    – Joffan
    Commented May 13, 2015 at 20:50
  • $\begingroup$ I just edited the question to add a crucial piece of information, we are not allowed to use in the problem Fermat's Little theorem or Euler's totient theorem. Any help with getting 3 and 4 without using Fermat's little would be so appreciated! $\endgroup$
    – user221400
    Commented May 14, 2015 at 4:50
  • $\begingroup$ #4 IS Fermat's Little Theorem. $\endgroup$
    – Joffan
    Commented May 14, 2015 at 15:07
  • $\begingroup$ See this question for proof of generalization of 3. We have $(a,p)=1\,\Rightarrow\, a^{p^{k-1}(p-1)}\equiv 1\pmod{\!p^k}$ for $k\ge 1$. $\endgroup$
    – user26486
    Commented May 14, 2015 at 18:07

3 Answers 3

Reset to default
1
$\begingroup$

$1.$ Use directly $\dbinom pk=\dfrac pk\dbinom{p-1}{k-1}\enspace(k>0)$. If $k<p$, it is coprime with $p$, hence it divides $\dbinom{p-1}{k-1}$. This proves $\dbinom pk$ is a multiple of $p$.

$2.$ $(1+ap)^p=1+p(ap)+\dbinom p2 (ap)^2+\dots+(ap)^p\equiv 1\mod p^2$.

$3.$ $a^{p(p-1)}=\bigl(a^{p-1}\bigr)^p\equiv 1^p=(1+kp)^p$ (Little Fermat), then use $1$.

$4.$ Little Fermat again.

$5.$ Binomial theorem and $1$.

Added: Without Little Fermat: we prove $4$ first.

By $1$, $a\mapsto a^p$ is a field homomorphism from $\mathbf Z/p\mathbf Z$ into itself. As it is a finite field, it is an automorphism , and the set of fixed points under this automorphism is a subfield. However $\mathbf Z/p\mathbf Z$ has no subfield but itself. Hence $a^p=a$ for any $a\in \mathbf Z/p\mathbf Z$, which is equivalent to $p\mid a^p-a$ for any $a\in\mathbf Z$.

Then $3$: by $4$, if $a\not\equiv 0\mod p$, $a^{p-1}\equiv 1 \mod p$ (this is indeed Little Fermat). Thus we can write $a^{p-1}=1+kp$ for some $k\in\mathbf Z$. By $2$, $$a^{p(p-1)}=(1+kp)^p\equiv1\mod p^2.$$

$\endgroup$
4
  • $\begingroup$ Is there any way to do this without using Fermat's little theorem? The question itself says to do it without using Fermat's little and I just can't understand how I'd go about doing that. Thanks so much for the help! $\endgroup$
    – user221400
    Commented May 14, 2015 at 4:13
  • $\begingroup$ @OliviaP. Little Fermat is trivial by induction. Clearly $0^p\equiv 0$ mod $p$. Assume $a^p\equiv a\pmod{\!p}$ for some $a$. Then $(a+1)^p\stackrel{\text{BT}}\equiv a^p+1\equiv a+1$ mod $p$, so we're done. BT is binomial theorem, together with 1. $\endgroup$
    – user26486
    Commented May 14, 2015 at 10:51
  • $\begingroup$ @Olivia: is Lagrange's theorem alllowed? $\endgroup$
    – Bernard
    Commented May 14, 2015 at 11:07
  • $\begingroup$ @user31415 I suggest you add the inductive FLT proof as an answer [modify "trivial" to "straightforward" though :-) ] $\endgroup$
    – Joffan
    Commented May 14, 2015 at 17:38
0
$\begingroup$

For part 1, write out $p\choose k$ in terms of factorials and think about what in the denominator could possibly cancel out the $p$ in the numerator.

$\endgroup$
0
$\begingroup$

  1. $$\binom pk=\frac{p!}{(p-k)!k!}$$ If $0<k<p$ then the factor $p$ in numerator does not get cancelled.

  2. $(ap+1)^p-1=\sum_{k=1}^{p}\binom pk (ap)^k$. Every term of the sum is clearly a multiple of $p^2$.

$\endgroup$

You must log in to answer this question.