[MIX][Teoria liczb] Mini-Mix

[mol_ksiazkowy]

1. Liczby Lucasa mozna określic z liczb Fibonacciego (\(\displaystyle{ F_1=F_2=1, \ F_{n+2}=F_{n+1}+F_n}\) dla n>0) wg
wzoru \(\displaystyle{ L_n =\frac{F_{2n}}{F_n}}\). Pokaż iz liczby \(\displaystyle{ L_n}\) sa naturalne, a dalej wykaz dwa wzory:
\(\displaystyle{ L_{2n}= L_n^2 -2(-1)^n}\)
\(\displaystyle{ 2F_{m+n}=F_mL_n + F_nL_m}\)

2. Wykaz, ze liczby postaci \(\displaystyle{ 8k+7}\), k=0, 1, ... nie da sie zapisac jako sumę trzech kwadratów liczb całkowitych. Nastepnie uogólnij to dla liczb \(\displaystyle{ 4^m(8k+7)}\) m=0,1,...czy prawdziwe jest twierdzenie odwrotne?

3. Niech dany bedzie ciag \(\displaystyle{ u_n}\) taki ze \(\displaystyle{ u_1=u_2=1, \ u_{n+2}=u_n^2 +u_{n+1}^2}\), dla n>0. Czy liczba \(\displaystyle{ u_{100}}\) dzieli sie przez 7. Jesli nie wyznacz reszte.

4. Zbadaj czy istnieja (w liczbach całkowitych ) rozwiazania równania \(\displaystyle{ a^2+b^2+c^2=a^2b^2}\) oprócz a=b=c=0

5. Wykaż, że jeśli \(\displaystyle{ p}\) jest liczba pierwsza postaci \(\displaystyle{ 4k+3}\) to \(\displaystyle{ \frac{p-1}{2}! \equiv 1 \ (mod \ p)}\) bądź \(\displaystyle{ \frac{p-1}{2}! \equiv -1 \ (mod \ p)}\). Ktora z tych alternatyw zachodzi gdy p=23 ?

6. Niech dane bedzie n t ze: \(\displaystyle{ n \equiv 1 \ (mod \ 6)}\). Wykaż że ułamek \(\displaystyle{ \frac{3}{n}}\) mozna zapisać w formie:
\(\displaystyle{ \frac{1}{a_1}+...+\frac{1}{a_k}}\), gdzie \(\displaystyle{ a_j >0}\) to liczby całkowite, parami rózne. Znajdż możliwie minimalna wartosc k.

7. a) Zbadaj czy równanie \(\displaystyle{ z^4-3y^4=x^2}\) ma rozwiazania w liczbach naturalnych
b) Wykaż, ze istnieje nieskonczenie wiele trójek \(\displaystyle{ x,y,z}\) t. ze \(\displaystyle{ x^4-y^4=z^3}\). I sprawdz, ze generuje je wzory
\(\displaystyle{ x=a^3(b^4-1)^2b}\)
\(\displaystyle{ y=a^3(b^4-1)^2}\)
\(\displaystyle{ z=a^4(b^4-1)^3}\)

8. Niech \(\displaystyle{ p}\) to liczba pierwsza >3. i weźmy wielomian \(\displaystyle{ p(x)=(x-1)(x-2)....(x-(p-1))}\).
Wykaż, że \(\displaystyle{ p^2 | p^\prime(0)}\).

9. Udowodnij, ze jeśli \(\displaystyle{ p, q}\) to liczby pierwsze >2, oraz \(\displaystyle{ q | 2^p -1}\), to wtedy:
\(\displaystyle{ \frac{q-1}{2p}}\) jest liczba naturalną

10. Niech \(\displaystyle{ p>5}\) to liczba pierwsza, i okresli sie zbiór \(\displaystyle{ S= \{ p-n^2 , : n \in N ,\ n^2 <p \}}\). Wykaz ze istnieja \(\displaystyle{ a, b \in S}\) t. ze \(\displaystyle{ 1< a< b}\) i \(\displaystyle{ a|b}\)


11. Wykaż, ze dla dowolnego \(\displaystyle{ n \in \{1, 2, ....\}}\) istnieje jeden jedyny wielomian o wspólczynnikach ze zbioru \(\displaystyle{ \{0,1...,8,9 \}}\), t. ze \(\displaystyle{ Q(-2)=Q(-5)=n}\)

[Artist]

AD 2
Najpierw wykażmy, że liczby postaci
\(\displaystyle{ 8k+7}\) nie mogą być zapisane w postaci trzech kwadratów liczb.

Załóżmy, że istnieją takie liczby całkowite x,y,z, że:
\(\displaystyle{ 8k+7=x^{2}+y^{2}+z^{2}}\) lewa strona jest nieparzyste, zatem, albo \(\displaystyle{ x,y,z}\) są nieparzyste, albo 2 z nich są parzyste a jedna nieparzysta.

Przypadek 1- wszystkie są nieparzyste:

Możemy zapisać że:
\(\displaystyle{ x=2p+1}\)
\(\displaystyle{ y=2r+1}\)
\(\displaystyle{ z=2q+1}\)

Po podniesieniu do potegi drugiej mamy:

\(\displaystyle{ x^{2}=(2p+1)^{2}=4p^{2}+4p+1=4p(p+1)+1}\)

Analogicznie można rozpisać y i z.

Zauważmy, że \(\displaystyle{ 4p(p+1)}\) jest podzielne przez 8, gdyż dla p parzystego \(\displaystyle{ 4p}\) będzie podzielne przez 8, zaś nieparzystego 4(p+1).

\(\displaystyle{ x^{2}\equiv1 \ (mod \ 8)}\)

Czyli po zsumowaniu \(\displaystyle{ x^{2}+y^{2}+z^{2}\equiv3 \ (mod \ 8)}\)
więc liczba może być postaci 8k+3.

Przypadek 2- dwie są parzyste.
W przypadku kwadratu liczby parzystej może on:
\(\displaystyle{ x=2b}\)
\(\displaystyle{ x^{2}=4b^{2}}\)
\(\displaystyle{ x^{2}\equiv0 \ (mod \ 8)}\) --gdy b dzieli sie przez 2;
\(\displaystyle{ x^{2}\equiv4 \ (mod \ 8)}\)
Reasumując możemy uzyskać, że liczby te mogą być postaci \(\displaystyle{ 8k+5}\), \(\displaystyle{ 8k+3}\) i \(\displaystyle{ 8k+1}\).

Nad drugą częścią jeszcze muszę pomyśleć ;P

Chyba tak będzie dobrze:
Załóżmy, że m jest najmniejszą liczbą dla której to wyrażenie jest prawdziwe:
\(\displaystyle{ 4^{m}*(8k+7)=x^{2}+y^{2}+z^{2}}\)
W odróżnieniu od części pierwszej lewa strona jest parzysta, gdyż m
eq 0 bo gdyby tak było to byśmy wrócili do części pierwszej.
Aby prawa strona była parzysta to albo wszystkie liczby x,y,z są parzyste, albo jedna z nich jest parzysta.
Przypadek 1- dwie nieparzyste:
Korzystając z części pierwszej wiemy, że liczby nieparzyste przy dzieleniu przez 8 dają resztę 1, a parzyste 0 lub 4 toteż liczba ta będzie postaci 8a+2 lub 8a+6 co przeczy założeniu. Muszę więc wszystkie być parzyste.
Przypadek 2-wszystkie parzyste
mamy zatem
\(\displaystyle{ 4^{m}(8k+7)=4p^{2}+4q^{2}+4r^{2}}\) dla p,q,r całkowitych;
po podzieleniu przez 4:
\(\displaystyle{ 4^{m-1}(8k+7)=p^{2}+q^{2}+r^{2}}\)



\(\displaystyle{ m>1}\) gdyż wtedy mielibyśmy 8k+7,,a to wiemy, że nie ma rozkładu na 3 kwadraty liczb naturalnych.
Zatem m-1 jest naturalne mniejsze od m co przeczy założeniu, że to m jest najmniejszą liczbą dla której równośc byłąby spełniona. Sprzeczność.

[Pablo09]

ok 3. -> Po wypisaniu kilku początkowych wyrazów widać, że tworzy się ciąg okresowy mod 7 :
\(\displaystyle{ u_{1}=1}\)
\(\displaystyle{ u_{2}=1}\)
\(\displaystyle{ u_{3}=2}\)
\(\displaystyle{ u_4=5\equiv 5 (mod 7)}\)
\(\displaystyle{ u_5=29\equiv 1 (mod 7)}\)
\(\displaystyle{ u_6\equiv 1^2+5^2=26\equiv 5 (mod 7)}\)
\(\displaystyle{ u_7\equiv 5 (mod 7)}\)
\(\displaystyle{ u_8\equiv1 (mod7)}\)
\(\displaystyle{ u_9\equiv 5 (mod7)}\)
\(\displaystyle{ ..}\)
stąd mamy , ze \(\displaystyle{ u_{100}}\) nie dzieli się przez 7, a reszta wynosi 5.

[michalg]

ad 1
Lemacik.
\(\displaystyle{ F_n^2 - F_{n+1}F_{n-1}=-1(-1)^n}\)
d-d indukcyjny
\(\displaystyle{ F_2^2-F_1F_3=-1}\)
krok indukcyjny:
\(\displaystyle{ F_n^2 - F_{n+1}F_{n-1}=F_n(F_{n-1}+F_{n-2})- F_{n+1}F_{n-1} = F_nF_{n-2} - F_{n-1}(F_{n+1}-F_{n})=-(F_{n-1}^2 - F_nF_{n-2})}\)

W rozwiązaniu zadania korzystam ze wzoru \(\displaystyle{ F_{m+n} = F_{m+1}F_n + F_mF_{n-1}}\)(*)
\(\displaystyle{ F_{2n}=F_{n+1}F_n + F_nF_{n-1}}\), więc liczba\(\displaystyle{ L_n=F_{n+1} + F_{n-1}}\) jest naturalna.

\(\displaystyle{ L_{2n}=F_{2n+1}+F_{2n-1}=F_{n+1}^2 + F_n^2 + F_n^2 + F_{n-1}^2}\)(skorzystałem z *)
\(\displaystyle{ F_{n+1}^2 + F_n^2 + F_n^2 + F_{n-1}^2 = (F_{n+1}+F_{n-1})^2+2F_n^2-2F_{n+1}F_{n-1}=L_n^2-2(-1)^n}\)(korzystałem z lemaciku)

\(\displaystyle{ F_{m+n} = F_{m+1}F_n + F_mF_{n-1}=F_{n+1}F_m + F_nF_{m-1}}\),więc
\(\displaystyle{ 2F_{m+n} = (F_{m+1}+F_{m-1})F_n + F_m(F_{n+1}+F_{n-1})=F_nL_m + L_nF_m}\)

[Pablo09]

9. Na początku zauważmy, ze q jest nieparzyste i że \(\displaystyle{ p\neq q}\)
z Małego Fermata \(\displaystyle{ q|2^{q-1}-1}\) czyli \(\displaystyle{ p|q-1}\) => \(\displaystyle{ pk=q-1}\)
\(\displaystyle{ \frac{q-1}{2p}=(q-1) \frac{k}{2(q-1)}=k/2}\)
a k jest parzyste (wynika zpk=q-1) , ckd

[ Dodano: 6 Sierpnia 2008, 12:07 ]

[mikel]

5.
tw. Wilsona: \(\displaystyle{ (p-1)!\equiv-1 (mod p)}\)
dla \(\displaystyle{ p=4k+3}\) mamy:
\(\displaystyle{ (p-1)!\equiv (4k+2)! \equiv 1\cdot2\cdot3\cdot...(2k+1)\underbrace{\cdot(-(2k+1)) (-2k)...(-2)\cdot(-1)}_{2k+1} \equiv -(( \frac{p-1}{2} )!)^2\equiv-1 (mod p)}\)
\(\displaystyle{ (( \frac{p-1}{2})!)^2-1\equiv 0 (mod p)}\)
\(\displaystyle{ (( \frac{p-1}{2})!-1)(( \frac{p-1}{2})!+1) \equiv 0 (mod p)}\)
z czego wynika, że \(\displaystyle{ ( \frac{p-1}{2})! \equiv 1 ( \frac{p-1}{2})! \equiv -1 (mod p)}\)

[michalg]

ad 4
\(\displaystyle{ c^2+1=(a^2-1)(b^2-1)}\) Liczby \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są zatem parzyste (w przeciwnym razie \(\displaystyle{ c^2}\) dawałoby resztę 3 przy dzieleniu przez 4). \(\displaystyle{ c}\) musi być liczbą parzystą (bo \(\displaystyle{ c^2+1}\) jest liczbą nieparzystą).
\(\displaystyle{ c=2c_1}\)
\(\displaystyle{ b=2b_1}\)
\(\displaystyle{ a=2a_1}\)
\(\displaystyle{ a_1^2 + b_1^2 + c_1^2= 4a_1^2b_1^2}\)
Wynika stąd, że liczby \(\displaystyle{ a_1}\),\(\displaystyle{ b_1}\),\(\displaystyle{ c_1}\) są wszystkie parzyste (bo ich suma dzieli się przez 4).
\(\displaystyle{ c_1=2c_2}\)
\(\displaystyle{ b_2=2b_2}\)
\(\displaystyle{ a_1=2a_2}\)
\(\displaystyle{ a_2^2 + b_2^2 + c_2^2= 16a_2^2b_2^2}\)
Liczby \(\displaystyle{ a_2}\),\(\displaystyle{ b_2}\),\(\displaystyle{ c_2}\) są wszystkie parzyste.
...
\(\displaystyle{ c_{n-1}=2c_{n}}\)
\(\displaystyle{ b_{n-1}=2b_{n}}\)
\(\displaystyle{ a_{n-1}=2a_{n}}\)
\(\displaystyle{ a_n^2 + b_n^2 + c_n^2= 4^na_n^2b_n^2}\)
Liczby \(\displaystyle{ a_n}\),\(\displaystyle{ b_n}\),\(\displaystyle{ c_n}\) są wszystkie parzyste.

Zatem nie może istnieć rozwiązanie zadanego równania, ponieważ wtedy istniałyby liczby całkowite dzielące się przez dowolnie duże potęgi liczby 2.

[King James]

8. Niech \(\displaystyle{ p}\) to liczba pierwsza >3. i weźmy wielomian \(\displaystyle{ p(x)=(x-1)(x-2)....(x-(p-1))}\).
Wykaż, że \(\displaystyle{ p^2 | p^\prime(0)}\).

\(\displaystyle{ p'(x)=\left(\prod_{i=1}^{p-1}(x-i)\right)'=\sum_{j=1}^{p-1}\prod_{i=1 \atop i\neq j }^{p-1}(x-i)=\sum_{j=1}^{p-1}\frac{1}{x-j}\prod_{i=1}^{p-1}(x-i)}\)
\(\displaystyle{ p'(0)=-\sum_{j=1}^{p-1}\frac{(-1)^{p-1}}{j}\prod_{i=1}^{p-1}i=(-1)^{p}(p-1)!\sum_{j=1}^{p-1}\frac{1}{j}=-p!\sum_{j=1}^{\frac{p-1}{2}}\frac{1}{j(p-j)}}\)

Wystarczy pokazać, że:

\(\displaystyle{ \sum_{j=1}^{\frac{p-1}{2}}\frac{1}{j(p-j)} \equiv -\sum_{j=1}^{\frac{p-1}{2}}\frac{1}{j^2} \equiv 0 \mod p}\)

Gdyby \(\displaystyle{ \frac {1}{i^2} \equiv \frac {1}{j^2} \mod{p}}\) dla pewnych \(\displaystyle{ i, j q \frac {p - 1}{2}}\) wtedy \(\displaystyle{ (i - j)(i + j) \equiv 0 \mod{p}}\) ale z tego, że \(\displaystyle{ i, j q \frac {p - 1}{2}}\) mamy \(\displaystyle{ i = j}\), liczby \(\displaystyle{ \frac {1}{j^2}}\) dla \(\displaystyle{ j = 1,2,...,\frac {p - 1}{2}}\) są wszystkimi resztami kwadratowymi modulo p, więc:

\(\displaystyle{ \sum_{j=1}^{\frac{p-1}{2}}\frac{1}{j^2} \equiv \sum_{j=1}^{\frac{p-1}{2}}j^2=\frac {p(p - 1)(p + 1)}{24} \equiv 0 \mod{p}}\)

[Sylwek]

ad. 6 \(\displaystyle{ \frac{3}{n}=\frac{1}{n}+\frac{2}{n}=\frac{1}{n} + \frac{2}{n+1}+ \frac{2}{n(n+1)}=\frac{1}{n}+\frac{1}{\frac{n+1}{2}}+\frac{1}{\frac{n(n+1)}{2}}}\)

Prosto pokazać, że gdy \(\displaystyle{ n\neq 1}\), to wszystkie mianowniki są całkowite i parami różne. Przypadek dla n=1 każdy może sam zrobić . k=1 odpada. Dla k=2 mamy: \(\displaystyle{ \frac{3}{25}=\frac{1}{10}+\frac{1}{50}}\) (a długo szukałem dowodu, że się nie da dla k=2...) - zatem minimalna wartość k to 2.

P.S. Każdą liczbę wymierną da się przedstawić w postaci sumy: \(\displaystyle{ \sum \frac{1}{a_i}}\), gdzie \(\displaystyle{ a_i}\) są parami różnymi liczbami całkowitymi - patrz: ułamek egipski.

[Wasilewski]

King James , korzystałeś po drodze z twierdzenia Wilsona? Bo w takim przypadku to mniej więcej rozumiem Twoje rozwiązanie; sam próbowałem podobnie, tylko zatrzymałem się na tym, jak wykazać, ze suma elementów odwrotnych do \(\displaystyle{ j^{2}}\) jest podzielna przez p. Jakbyś mógł dokładniej wyjaśnić (albo ktoś inny), jak przeszedłeś od sumy elementów odwrotnych do sumy tychże elementów to byłbym wdzięczny.

[mol_ksiazkowy]

Ładnie, szybko i sprawnie! ad 1, to Liczby lucasa są całkowite, bo \(\displaystyle{ \frac{F_{2n}}{F_n}= F_{n+1}+F_{n-1}}\) dla n=1, 2,... ad 6a istnieje uogólnienie równanie \(\displaystyle{ x^4-py^4=z^2}\) nie ma rozwiazan w l.naturalnych, gdy \(\displaystyle{ n \equiv 3 \ (mod \ 8)}\) , ad 7b - wszyscy sprawdzili "w pamieci".... Wyglad na to iż niemal wszystko skminione, zostały tylko:
10 i 11
no i 5
Ktora z tych alternatyw zachodzi gdy p=23 ?

[Wasilewski]

To wystarczy w pary połączyć (rozpatruję modulo 23):
4 i 6 -> 1
3 i 8 -> 1
2 i 11 -> -1
7 i 10 ->1
5 i 9 ->-1
Czyli 1.

[andkom]

Ależ molu, może źle widzę, ale za 7. to się jeszcze nikt nie zabrał (ale ja też nie o tym, tylko o innym).

11.
Zrobię więcej: pokażę, że jeśli k,l są całkowite oraz 3|k-l, to istnieje dokładnie jeden wielomian W o współczynnikach ze zbioru {0,1,2,3,4,5,6,7,8,9} taki, że W(-2)=k oraz W(-5)=l.

Założenie, że 3|k-l jest potrzebne, bo jeśli wielomian W spełnia to, co jest napisane wyżej, to
3=-2-(-5)|W(-2)-W(-5)=k-l

-------------------------------------------------------------------------------------

Najpierw istnienie:
Niech K={-3,-2,-1,0,1,2,3,4,5,6}, L={0,1}.
Ręcznie załatwmy pary k,l takie, że \(\displaystyle{ k\in K}\), \(\displaystyle{ l\in L}\) oraz 3|k-l:
k=-3, l=0 \(\displaystyle{ W(x)=x^2+6x+5}\)
k=0, l=0 \(\displaystyle{ W(x)=0}\)
k=3, l=0 \(\displaystyle{ W(x)=x+5}\)
k=6, l=0 \(\displaystyle{ W(x)=x^3+6x^2+5x}\)
k=-2, l=1 \(\displaystyle{ W(x)=x^2+6x+6}\)
k=1, l=1 \(\displaystyle{ W(x)=1}\)
k=4, l=1 \(\displaystyle{ W(x)=x+6}\)

Rozważmy operację polegającą na tym, że liczbie k przyporządkowywać będziemy jedną z liczb \(\displaystyle{ \frac{a-k}2}\), gdzie \(\displaystyle{ a\in\{0,1,2,3,4,5,6,7,8,9\}}\) jest takie, że 2|a-k. Zobaczymy, że dla dowolnej liczby k, po pewnej liczbie kroków polegających na przykładaniu naszej operacji, niezależnie od tego, jakie są liczby a w poszczególnych krokach, w końcu trafimy do K i już stamtąd nie wyjdziemy.
Jeśli |k|>9, to
\(\displaystyle{ \left|\frac{a-k}2\right|\leqslant\frac{|k|+a}2\leqslant\frac{|k|+9}2=|k|+\frac{9-|k|}2}\)

[mol_ksiazkowy]

andkom napisal

Ależ molu, może źle widzę, ale za 7. to się jeszcze nikt nie zabrał (ale ja też nie o tym, tylko o innym).

Oh, jak tak to okey, Swietnie nawet nie myslałem ze tak szybko pojdzie z tym ostatnim, Brawo andkom, trzeba sie tu było "troszke" napracowac! Abyło to zadanie z dosc dawnych olimpijskich z USA, treningowe


Inny zapis do zad, 4
załozmy ze istnieja \(\displaystyle{ a, b, c}\) takie ze spełniaj to równanie i \(\displaystyle{ abc 0}\). Wezmy mozliwie najwieksze k, t ze \(\displaystyle{ a=2^ku, \ b=2^kv, \ c=2^kw}\) tj któras z liczb u, v, w jest nieparzysta. Skoro \(\displaystyle{ u^2+v^2+w^2=4^ku^2v^2}\) wiec lewa strona nie dzieli sie na 4, tj k=0. w efekcie a=u, b=v, c=w i dokładnie jedna z tych liczb jest nieparzysta. Wiec \(\displaystyle{ c^2+1=(a^2-1)(b^2-1)}\) dzieli sie na 8, a to sprzecznosc.

[TomciO]

To nie było zadanie treningowe tylko było na olimpiadzie po prostu (rok 1997).

Jesli chodzi o zadanie 10, niech \(\displaystyle{ a = [\sqrt{p}]}\). Zauważmy, że jeśli \(\displaystyle{ (p - (a^2 + a))^2 < p}\) to wówczas
\(\displaystyle{ p - (p - (a^2+a))^2 = (p-a^2)(a^2+2a-1)}\)
(albo coś podobnego). Zatem wystarczy sprawdzić tamtą nierówność. Niech \(\displaystyle{ p = k^2 + r}\), gdzie \(\displaystyle{ r q 2k}\). Wówczas \(\displaystyle{ a = k}\) i nierówność przybiera postać
\(\displaystyle{ (r-k)^2 < k^2 + r}\)
lub
\(\displaystyle{ r^2 < 2kr + r}\)
a to jest prawda bo \(\displaystyle{ 2k+1 < r}\).