I have solved part of this exercise until it got too difficult for me. Nice if you have some feedback on what I have managed to do.
In this exercise $p \gt 2 $ is prime. If a and b are whole numbers, we write $a \equiv b$ if a-b is divisible by p.
a) Assume that n and m are whole numbers such that n is not divisible by p. Show that if pm/n is a whole number, it is divisible by p (Hint: Use the fundamental theorem of arithmetic).
My answer: Because n is not divisible by p it is not possible to reduce the fraction by p. Because pm/n is a whole number, m/n must be a whole number. That means that m is divisible by n and can be reduced. pm/n can therefore be written pt and is thus divisible by p.
I haven't used the fundamental theorem of arithmetic. Does this mean that my answer is not rigorous?
b) Show that if $0 \lt k \lt p$ then $\binom {p}{k}$ is divisible by p.
Answer: We can exclude k=0 and k=p which would mean $\binom {p}{k}=1$.
The expression $\binom {p}{k}=\frac{p!}{k!(p-k)!}$ will be divisible by p as long as it is not reduced by p, which is the case for k=0 and k=p. k! and (p-k)! are always less than p!, and never reduces the p.
c) Show that $(a+1)^p\equiv a^p +1$
My answer
$(a+1)^p=\sum_{k=0}^{p} \binom{p}{k}a^k1^{p-k}$
$(a+1)^p - (a^p +1)=\sum_{k=1}^{p-1} \binom{p}{k}a^k1^{p-k}$
The terms in $\sum_{k=1}^{p-1}$ are reducible by p. The expression $\binom {p}{k}=\frac{p!}{k!(p-k)!}$ is only irreducible by p as long as k=1 and k=p Thus $(a+1)^p \equiv a^p +1$
d) Show by induction on a that $a^p \equiv a$ for all natural numbers a. Explain why the formula also holds when a is 0 or negative.
My answer: The formula holds for a=1: $1^p=1$
I need to prove that the formula holds for $(a+1)^p \equiv (a+1)$ which is what we proved in c). Because of that the formula holds true for all a.
I'm not able to solve the following:
e) Show that if a is not divisible by p, then $a^{p-1} \equiv 1$. This is called Fermat's little theorem and is a very useful tool within number theory.
f) Show that if n is not divisible by 5, then $n^8 -1$ is divisible by 5.
g) Show that $3n^7 + 4n$ is divisible by 7 for all $n \in \mathbb{Z}$
My answer:
For n=1: $3n^7 + 4n=7$
$3(n+1)^7 + 4(n+1)$
$=3n^7 + 4n=3n^7 + 3 + 3\sum_{k+1}^{6} \binom {7}{k} + 4(n+1) $ $=(3n^7 + 4n) + 7 + 3\sum_{k+1}^{6} \binom {7}{k}$
Every term in $\sum_{k=1}^{6} \binom {7}{k}$ is reducible by 7 because the factor 7 in 7! hasn't been reduced as in k=0 and k=7. The terms $3n^7 + 4n$ are divisible by 7 from our induction assumption. The term 7 is obviously divisibly by 7. Thus $=(3n^7 + 4n) + 7 + 3\sum_{k+1}^{6} \binom {7}{k}$ is divisible by 7.
I have the solution for e) and f), if anyone is interested.
e) From d) we have $a^p \equiv a$
$a^p -a \equiv 0 $
$a(a^{p-1} -1) \equiv 0 $
Which means that either a or $(a^{p-1} -1)$ is divisible by p.
In the case that a is not divisible by p, $(a^{p-1} -1)$ must be divisible by p.
f)
$n^4 \equiv 1 \mod 5$
$(n^4-1)(n^4+1) \equiv 0 \mod 5$
$n^8-1 \equiv 0 \mod 5$