[Teoria liczb] kilka zadań

[artii94]

Cześć
Zamieszczam parę fajnych zadanek z teorii liczb
1.Udowodnij, że jeśli p jest liczbą pierwszą, to \(\displaystyle{ p|a^{p}-b^{p} \Rightarrow p^{2}|a^{p}-b^{p}}\)
2. Udowodnij że jeśli \(\displaystyle{ k|a^{n}-1}\) i \(\displaystyle{ k|a^{m}-1}\) to \(\displaystyle{ k|a^{NWD(n,m)}-1}\)(chciałbym zobaczyć sposób, bądź nakierowanie bez użycia eulera)
3.Udowodnij, że nie istnieje takie całkowite n, że \(\displaystyle{ n|2^{n}-1}\)
4.Udowodnij, że dla dowolnej liczby naturalnej \(\displaystyle{ n}\) i dowolnej liczby naturalnej nieparzystej k suma \(\displaystyle{ 1^{k}+2^{k}+...n^{k}}\) dzieli się przez \(\displaystyle{ 1+2+...+n}\)
5.Udowodnij, że\(\displaystyle{ \frac{a^{3}+2a}{a^{4}+3a^{2}+1}}\) jest ułamkiem nieskracalnym.
Pozdrowienia

[Swistak]

1. Mały Fermat i dwumian Newtona
2. Coś ala algorytm Euklidesa
3. Rzędy + najmniejszy dzielnik pierwszy
4. Pogrupować wyrazy po prawej stronie i wyjdzie.
5. Not so hard.

[cyberciq]

3. zał. n>1 chyba jeszcze.

[ares41]

1. Mały Fermat i dwumian Newtona

Można ominąć dwumian Newtona od razu zapisując \(\displaystyle{ a^p-b^p=a \cdot a^{p-1}-b \cdot b^{p-1}\equiv a-b\pmod{p}}\) i dalej \(\displaystyle{ a\equiv b\pmod{p}}\).

[JaQb]

1. Mały Fermat i dwumian Newtona

Można ominąć dwumian Newtona od razu zapisując \(\displaystyle{ a^p-b^p=a \cdot a^{p-1}-b \cdot b^{p-1}\equiv a-b\pmod{p}}\) i dalej \(\displaystyle{ a\equiv b\pmod{p}}\).

I co potem?

[timon92]

potem dwumian Newtona

[adamm]

Nie mieszajcie chłopakowi w głowie, 1. idzie tylko z LTE. 5. not so hard but still Euklides ;p

[ares41]

I co potem?

\(\displaystyle{ a^p-b^p=(a-b) \sum_{k=1}^{p} a^{p-k}b^{k-1}\\ \\ \sum_{k=1}^{p} a^{p-k}b^{k-1}\equiv pa^{p-1}\pmod{p}}\)
Potem korzystając z założeń i z tego, że \(\displaystyle{ a\equiv b \pmod{p} \Leftrightarrow \bigvee_{m\in\mathbb{Z}}a-b=mp}\) dostajemy \(\displaystyle{ ma^{p-1}p^2\equiv 0\pmod{p}}\)

[artii94]

Dobra ale odnośnie 5, to ja to zrobiłem tak, skoro
\(\displaystyle{ NWD(a^3+2a;a^{4}+3a^{2}+1) \le NWD(a(a^2+2)(a^2+1);a^4+3a^3+1)}\)
a skoro \(\displaystyle{ NWD((a^2+2)(a^2+1);a^4+3a^2+1)=1}\), oraz \(\displaystyle{ NWD(a;a^4+3a^3+1)=1}\) to otrzymujemy, że
\(\displaystyle{ NWD(a^3+2a;a^{4}+3a^{2}+1)=1}\) (Czy to jest dobrze i czy ktoś jak coś może pokazać jakieś inne rozwiązania tego zadania, a konkretnie tego typu zadania)
Nie wiem jednak co zrobić z 4
bo mam że ta nasza suma z potęgami ma się dzielić przez \(\displaystyle{ \frac{n(n+1)}{2}}\), ale nie wiem co dalej.

[Panda]

W \(\displaystyle{ 4.}\) pogrupuj i zapisz jako iloczyny \(\displaystyle{ n}\) i jeszcze czegoś, potem to samo dla \(\displaystyle{ n+1}\); rozważ parzystość \(\displaystyle{ n}\) w razie czego.


W \(\displaystyle{ 5.}\) korzystaj swawolnie z \(\displaystyle{ NWD(a,b) = NWD(a,b-a)}\), indukcyjnie \(\displaystyle{ NWD(a,b) = NWD(a, b - ka)}\), oczywiście jeśli wszystko dodatnie. Ładnie się wszystko poodejmuje raz z jednej raz z drugiej i wyjdzie \(\displaystyle{ 1}\). Twojego nie ogarniałem, więc nie wiem czy dobre.

[cyberciq]

artii94, możesz też w 5 także założyć sobie, że te liczby mają jakiś wspólny dzielnik \(\displaystyle{ d>1}\) i dojść do sprzeczności rozpatrując odpowiednie podzielności.

[artii94]

hmm jakoś dalej te 4 nie pada, czy może ktoś dać jakiegoś hinta?

[Panda]

\(\displaystyle{ 1^{k} + n^{k} = (1+n)(...)}\)
\(\displaystyle{ 2^{k} + (n-1)^{k} = (n+1)(...)}\)


Dla przypadku \(\displaystyle{ n}\) nieparzystego coś tam w środku zostanie, ale będzie podzielne przez \(\displaystyle{ \frac{n+1}{2}}\).
Analogicznie postąp żeby wyłączyć \(\displaystyle{ n}\), wtedy po prostu paruj zostawiając na końcu \(\displaystyle{ n^{k}}\).