[MIX][Teoria liczb] Zestaw od Iwana
: 2 maja 2009, o 18:19
1. a Obliczyć -stosując algorytm Euklidesa \(\displaystyle{ NWD(6188,4709)}\).
b Obliczyć -dowolną metoda \(\displaystyle{ NWD(81719, 52003, 33649,30107)}\)
2. Znaleźć resztę z dzielenia \(\displaystyle{ (12371^{56} +34)^{28}}\) przez \(\displaystyle{ 111}\)
3. Dowieść, że kongruencja \(\displaystyle{ x^2+1 \equiv 0 \ ( mod \ p)}\) ma rozwiązanie wtedy i tylko wtedy, gdy \(\displaystyle{ p}\) ma postać \(\displaystyle{ 4m+1}\)
zaś
kongruencja \(\displaystyle{ x^2+2 \equiv 0 ( \ mod \ p)}\) ma rozwiązanie wtedy i tylko wtedy, gdy \(\displaystyle{ p}\) ma postać \(\displaystyle{ 8m+1}\) lub \(\displaystyle{ 8m+3}\)
4. Czy liczba \(\displaystyle{ 2^{1093}-2}\) jest podzielna przez \(\displaystyle{ 1093^{2}}\) ?
5. Niech \(\displaystyle{ n}\) bedzie liczba naturalną. Dowieść, ze wszystkie współczynniki rozwiniecia dwumianu Newtona \(\displaystyle{ (a+b)^n}\) są nieparzyste wtedy i tylko wtedy, gdy \(\displaystyle{ n}\) ma postać
\(\displaystyle{ 2^k -1}\) dla pewnego k
6. Znaleźć rozwinięcie kanoniczne liczby \(\displaystyle{ 244 \ 943 \ 325}\)
7. Rozwiąż ukłąd kongruencji
\(\displaystyle{ \begin{cases} 3x+4y-29 \equiv 0 \ (mod \ 143) \\ 2x-9y+84 \equiv 0 \ (mod \ 143) \end{cases}}\)
8. a Wyznacz pierwiastki pierwotne liczby \(\displaystyle{ p=41}\)
b Dowieść, że liczba 3 jest pierwiastkiem pierwotnym liczby pierwszej postaci \(\displaystyle{ 2^n p +1}\), gdzie \(\displaystyle{ n>1}\) i \(\displaystyle{ p > \frac{3^{2^{n-1}}}{2^n}}\)
9. Obliczyć jak najprostszym sposobem wykładnik, do którego należy liczba \(\displaystyle{ 7}\) według modułu \(\displaystyle{ 43}\)
10. Niech \(\displaystyle{ s=\frac{1}{3} +\frac{1}{5} +\frac{1}{7} +....+\frac{1}{2n+1}}\), dla n>0. Wykaż, że \(\displaystyle{ s}\) nie jest liczbą całkowitą
11. a Znaleźć wykladnik potęgi, w której czynnik \(\displaystyle{ 5}\) występuje w rozkładzie kanonicznym liczby \(\displaystyle{ 5258!}\)
b Znaleźć rozkład kanoniczny liczby \(\displaystyle{ 125!}\)
12. Uzywając symbolu Legendre'a zbadaj czy kongruencja ma rozwiązania (i ile?) \(\displaystyle{ x^2 \equiv 219 \ (mod \ 383)}\)
13. Rozważmy ciąg złożony z 286 liczb:
\(\displaystyle{ 1*2....*10, \ 2*3....*11, \ 3*4....*12, \ ....., \ 285*286*....*294, \ 286*287*....*295}\)
Ile jest w tym ciągu liczb będących wielokrotnościami liczby 143 ?
14.Niech \(\displaystyle{ k}\) będzie liczbą naturalną, zaś \(\displaystyle{ d}\) przebiega liczby spełniające warunki \(\displaystyle{ d>0}\) i \(\displaystyle{ \phi(d)=k}\). Wykaż, ze
\(\displaystyle{ \sum_{d} \mu(d) =0}\), gdzie \(\displaystyle{ \mu()}\) jest funkcją Mobiusa
15. Dana jest forma \(\displaystyle{ 3^nx_n + 3^{n-1}x_{n-1}+...+3x_{1}+3^{0}x_{0}}\)., gdzie każda z liczb \(\displaystyle{ x_n, x_{n-1}, ...., x_1, x_0}\) niezależnie od pozostałych przebiega wartości \(\displaystyle{ -1,0,1}\). Dowieść, że ta forma wyraża wszystkie liczby:
\(\displaystyle{ -H, ...., -1, 0, 1, ...., H}\) , gdzie \(\displaystyle{ H= \frac{3^{n+1}-1}{2}}\)
i to każda liczbę jednym tylko sposobem.
Gdy \(\displaystyle{ n=5}\) podaj rozkład liczby \(\displaystyle{ 152}\).
16. a Podaj kongruencję 7 go stopnia, w której współczynnik przy najwyższej potędze niewiadomej równy jest 1, i która jest równoważna z kongruencją:
\(\displaystyle{ 2x^7+ x^3+4 \equiv 0 \ (mod \ 7)}\)
b Z jaką kongruencją stopnia < 5 jest równoważna kongruencja
\(\displaystyle{ 3x^{14}+4x^{13}+3x^{12}+2x^{11}+x^{9}+ 2x^{8}+4x^{7}+ x^{6}+3x^{4}+x^{3}+4x^{2}+2x \equiv 0 \ (mod \ 5)}\)?
17.a Wypisz wszystkie reszty kwadratowe dla modułu \(\displaystyle{ p=11}\)
b Podaj największą nieresztę kwadratowa (jest ich 8) dla modułu \(\displaystyle{ p=17}\)
18. a Jaka jest reszta z dzielenia \(\displaystyle{ {28 \choose 14}}\) przez 29 ?
b Jaka jest reszta z dzielenia \(\displaystyle{ \frac{2^{31}-2}{31}}\) przez 31 ?
19. Niech \(\displaystyle{ n>0}\), a \(\displaystyle{ T}\) niech bedzie liczbą punktów kratowych, obszaru \(\displaystyle{ x>0, y>0, \ xy \leq n}\). Dowieść, że
\(\displaystyle{ T=2 \sum_{0 <x \leq \sqrt{n}} \lceil \frac{n}{x} \rceil - (\lceil \sqrt{n} \rceil)^2}\)
20*. Znależć cztery takie liczby naturalne, aby suma każdych dwóch spośród nich była pełnym kwadratem. (Jest to uogólnienie zadania Diofantosa dla trzech liczb, - wtedy mozna wziasc np. 41, 80, 320).
21*. Wyznaczyć wszystkie trójki \(\displaystyle{ x,y,z}\) liczb całkowitych takie, że liczby
\(\displaystyle{ x^2+y, \ y^2+z, \ z^2+x}\)
są kwadratami liczb całkowitych
22. Wykazać, ze dla każdej liczby pierwszej \(\displaystyle{ p}\) istnieją co najwyżej dwie liczby naturalne \(\displaystyle{ n}\), dla których wartość wyrażenia \(\displaystyle{ p2^n+1}\) jest kwadratem liczby naturalnej. Wyznaczyć wszystkie liczby pierwsze, dla których istnieją dokładnie dwie takie liczby.
23. Używając tw Wilsona wykaż, ze: na to aby liczba \(\displaystyle{ p>1}\) była pierwsza potzreba i wystarcza, aby \(\displaystyle{ (p-2)! \equiv 1 \ (mod \ p)}\)
Komentarz
Dla tych co lubia teorie liczb, Zadania pochodza (z wyjatkiem dwoch oznaczonych gwiazdka)- z ksiazki Iwan Winogradow, "Elementy teorii liczb" PWN, 1954 r. i są ciekawe.
Zapraszam wszystkich do rozwiazywania
Powodzenia !
b Obliczyć -dowolną metoda \(\displaystyle{ NWD(81719, 52003, 33649,30107)}\)
2. Znaleźć resztę z dzielenia \(\displaystyle{ (12371^{56} +34)^{28}}\) przez \(\displaystyle{ 111}\)
3. Dowieść, że kongruencja \(\displaystyle{ x^2+1 \equiv 0 \ ( mod \ p)}\) ma rozwiązanie wtedy i tylko wtedy, gdy \(\displaystyle{ p}\) ma postać \(\displaystyle{ 4m+1}\)
zaś
kongruencja \(\displaystyle{ x^2+2 \equiv 0 ( \ mod \ p)}\) ma rozwiązanie wtedy i tylko wtedy, gdy \(\displaystyle{ p}\) ma postać \(\displaystyle{ 8m+1}\) lub \(\displaystyle{ 8m+3}\)
4. Czy liczba \(\displaystyle{ 2^{1093}-2}\) jest podzielna przez \(\displaystyle{ 1093^{2}}\) ?
5. Niech \(\displaystyle{ n}\) bedzie liczba naturalną. Dowieść, ze wszystkie współczynniki rozwiniecia dwumianu Newtona \(\displaystyle{ (a+b)^n}\) są nieparzyste wtedy i tylko wtedy, gdy \(\displaystyle{ n}\) ma postać
\(\displaystyle{ 2^k -1}\) dla pewnego k
6. Znaleźć rozwinięcie kanoniczne liczby \(\displaystyle{ 244 \ 943 \ 325}\)
7. Rozwiąż ukłąd kongruencji
\(\displaystyle{ \begin{cases} 3x+4y-29 \equiv 0 \ (mod \ 143) \\ 2x-9y+84 \equiv 0 \ (mod \ 143) \end{cases}}\)
8. a Wyznacz pierwiastki pierwotne liczby \(\displaystyle{ p=41}\)
b Dowieść, że liczba 3 jest pierwiastkiem pierwotnym liczby pierwszej postaci \(\displaystyle{ 2^n p +1}\), gdzie \(\displaystyle{ n>1}\) i \(\displaystyle{ p > \frac{3^{2^{n-1}}}{2^n}}\)
9. Obliczyć jak najprostszym sposobem wykładnik, do którego należy liczba \(\displaystyle{ 7}\) według modułu \(\displaystyle{ 43}\)
10. Niech \(\displaystyle{ s=\frac{1}{3} +\frac{1}{5} +\frac{1}{7} +....+\frac{1}{2n+1}}\), dla n>0. Wykaż, że \(\displaystyle{ s}\) nie jest liczbą całkowitą
11. a Znaleźć wykladnik potęgi, w której czynnik \(\displaystyle{ 5}\) występuje w rozkładzie kanonicznym liczby \(\displaystyle{ 5258!}\)
b Znaleźć rozkład kanoniczny liczby \(\displaystyle{ 125!}\)
12. Uzywając symbolu Legendre'a zbadaj czy kongruencja ma rozwiązania (i ile?) \(\displaystyle{ x^2 \equiv 219 \ (mod \ 383)}\)
13. Rozważmy ciąg złożony z 286 liczb:
\(\displaystyle{ 1*2....*10, \ 2*3....*11, \ 3*4....*12, \ ....., \ 285*286*....*294, \ 286*287*....*295}\)
Ile jest w tym ciągu liczb będących wielokrotnościami liczby 143 ?
14.Niech \(\displaystyle{ k}\) będzie liczbą naturalną, zaś \(\displaystyle{ d}\) przebiega liczby spełniające warunki \(\displaystyle{ d>0}\) i \(\displaystyle{ \phi(d)=k}\). Wykaż, ze
\(\displaystyle{ \sum_{d} \mu(d) =0}\), gdzie \(\displaystyle{ \mu()}\) jest funkcją Mobiusa
15. Dana jest forma \(\displaystyle{ 3^nx_n + 3^{n-1}x_{n-1}+...+3x_{1}+3^{0}x_{0}}\)., gdzie każda z liczb \(\displaystyle{ x_n, x_{n-1}, ...., x_1, x_0}\) niezależnie od pozostałych przebiega wartości \(\displaystyle{ -1,0,1}\). Dowieść, że ta forma wyraża wszystkie liczby:
\(\displaystyle{ -H, ...., -1, 0, 1, ...., H}\) , gdzie \(\displaystyle{ H= \frac{3^{n+1}-1}{2}}\)
i to każda liczbę jednym tylko sposobem.
Gdy \(\displaystyle{ n=5}\) podaj rozkład liczby \(\displaystyle{ 152}\).
16. a Podaj kongruencję 7 go stopnia, w której współczynnik przy najwyższej potędze niewiadomej równy jest 1, i która jest równoważna z kongruencją:
\(\displaystyle{ 2x^7+ x^3+4 \equiv 0 \ (mod \ 7)}\)
b Z jaką kongruencją stopnia < 5 jest równoważna kongruencja
\(\displaystyle{ 3x^{14}+4x^{13}+3x^{12}+2x^{11}+x^{9}+ 2x^{8}+4x^{7}+ x^{6}+3x^{4}+x^{3}+4x^{2}+2x \equiv 0 \ (mod \ 5)}\)?
17.a Wypisz wszystkie reszty kwadratowe dla modułu \(\displaystyle{ p=11}\)
b Podaj największą nieresztę kwadratowa (jest ich 8) dla modułu \(\displaystyle{ p=17}\)
18. a Jaka jest reszta z dzielenia \(\displaystyle{ {28 \choose 14}}\) przez 29 ?
b Jaka jest reszta z dzielenia \(\displaystyle{ \frac{2^{31}-2}{31}}\) przez 31 ?
19. Niech \(\displaystyle{ n>0}\), a \(\displaystyle{ T}\) niech bedzie liczbą punktów kratowych, obszaru \(\displaystyle{ x>0, y>0, \ xy \leq n}\). Dowieść, że
\(\displaystyle{ T=2 \sum_{0 <x \leq \sqrt{n}} \lceil \frac{n}{x} \rceil - (\lceil \sqrt{n} \rceil)^2}\)
20*. Znależć cztery takie liczby naturalne, aby suma każdych dwóch spośród nich była pełnym kwadratem. (Jest to uogólnienie zadania Diofantosa dla trzech liczb, - wtedy mozna wziasc np. 41, 80, 320).
21*. Wyznaczyć wszystkie trójki \(\displaystyle{ x,y,z}\) liczb całkowitych takie, że liczby
\(\displaystyle{ x^2+y, \ y^2+z, \ z^2+x}\)
są kwadratami liczb całkowitych
22. Wykazać, ze dla każdej liczby pierwszej \(\displaystyle{ p}\) istnieją co najwyżej dwie liczby naturalne \(\displaystyle{ n}\), dla których wartość wyrażenia \(\displaystyle{ p2^n+1}\) jest kwadratem liczby naturalnej. Wyznaczyć wszystkie liczby pierwsze, dla których istnieją dokładnie dwie takie liczby.
23. Używając tw Wilsona wykaż, ze: na to aby liczba \(\displaystyle{ p>1}\) była pierwsza potzreba i wystarcza, aby \(\displaystyle{ (p-2)! \equiv 1 \ (mod \ p)}\)
Komentarz
Dla tych co lubia teorie liczb, Zadania pochodza (z wyjatkiem dwoch oznaczonych gwiazdka)- z ksiazki Iwan Winogradow, "Elementy teorii liczb" PWN, 1954 r. i są ciekawe.
Zapraszam wszystkich do rozwiazywania
Powodzenia !