Teoria liczb - zadania Marzantowicz, Zarzycki

[kati96xd]

Dzień dobry,
Mam problem z paroma zadaniami. Pochodzą one z książki Marzantowicza i Zarzyckiego "Elementy teorii liczb". Niestety w książce nie ma podanych rozwiązań, ani chociażby wskazówek.

Zad. 1
Niech \(\displaystyle{ p,q}\) będą różnaymi liczbami pierwszymi oraz \(\displaystyle{ a^{p}\equiv a \pmod{p}}\) i
\(\displaystyle{ a^{q}\equiv a \pmod{q}}\). Wykaż, że \(\displaystyle{ a^{pq}\equiv a \pmod{pq}}\).

Zad. 2
Załóżmy, ze \(\displaystyle{ p,q}\) są nieparzystymi liczbami pierwszymi oraz \(\displaystyle{ p-1|q-1}\). Wykaż, że jeśli \(\displaystyle{ NWD(a,pq)=1}\) to \(\displaystyle{ a^{q-1}\equiv 1 \pmod{pq}}\).

Zad. 3
Udowodnij, że każda liczba calkowita spelnia co najmniej jedną z sześciu kongruencji:
\(\displaystyle{ x\equiv 0 \pmod{2}}\), \(\displaystyle{ x\equiv 1 \pmod{4}}\), \(\displaystyle{ x\equiv 3 \pmod{8}}\), \(\displaystyle{ x\equiv 1 \pmod{3}}\), \(\displaystyle{ x\equiv 3 \pmod{12}}\), \(\displaystyle{ x\equiv 23 \pmod{24}}\)

Zad. 4.
Niech p będzie liczbą pierwszą większą od 3 i niech
\(\displaystyle{ f(x)=(x-1)(x-2) \cdot \cdot \cdot (x-p+1)}\)
Wykaż, że \(\displaystyle{ p^{2}|f^{'}(0)}\).

Zad. 5
Wykazać, że jeśli p jest nieparzystą liczbą pierwszą oraz \(\displaystyle{ a+b=p-1}\) to
\(\displaystyle{ a!b! + (-1)^{a}\equiv 0 \pmod{p}}\)

[mol_ksiazkowy]

3
Nie wprost; założyć ze \(\displaystyle{ x=24k +r}\) itd. (Jakie bedzie \(\displaystyle{ r}\) ?)

[Premislav]

Zadanie 1.
Zauważ, że ponieważ \(\displaystyle{ (p,q)=1}\), więc wystarczy uzasadnić, iż
\(\displaystyle{ p|a^{pq}-a}\) i \(\displaystyle{ q|a^{pq}-a}\)
oraz skorzystać z bardzo znanego lematu, że jeśli
\(\displaystyle{ (p,q)=1}\), to \(\displaystyle{ p| c\wedge q|c \Rightarrow pq |c}\)-- 13 maja 2017, o 17:10 --Zadanie 5.

\(\displaystyle{ \textbf{Lemat}}\) (bardzo prosty)
Dla dowolnego \(\displaystyle{ p \in \PP}\) (zbiór liczb pierwszych) i \(\displaystyle{ k \in \left\{ 1,2\dots p-1\right\}}\) mamy
\(\displaystyle{ {p-1 \choose k} \equiv (-1)^k \pmod{p}}\)

\(\displaystyle{ \textbf{Dowód lematu}}\)

Równoważnie mamy
\(\displaystyle{ (p-1)(p-2)\dots(p-k) \equiv (-1)^k k! \pmod{p}}\)
bo \(\displaystyle{ (k!, p)=1}\) gdyż \(\displaystyle{ k<p}\).
A teraz wystarczy zauważyć, że:
\(\displaystyle{ p-1 \equiv-1 \pmod{p}\\p-2\equiv -2\pmod{p}\\\dots\\p-k \equiv -k \pmod{p}}\)
Następnie mnożymy te kongruencje stronami, co kończy dowód lematu.

Proszę spróbować skorzystać z powyższego lematu w celu rozwiązania zadania.
Wskazówka: \(\displaystyle{ {a+b \choose a}=\frac{(a+b)!}{a!b!}}\)
Kolejna wskazówka: z Wilsona \(\displaystyle{ (p-1)!\equiv -1\pmod{p}}\)