[MIX][Teoria liczb] Zestaw od Iwana

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 6023
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2507 razy
Pomógł: 668 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: mol_ksiazkowy » 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)}\)


:arrow: :arrow: Komentarz
:arrow: Dla tych co lubia teorie liczb, :arrow: 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 ! :D
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Artist
Użytkownik
Użytkownik
Posty: 865
Rejestracja: 27 sty 2008, o 21:07
Płeć: Mężczyzna
Lokalizacja: Brodnica
Podziękował: 27 razy
Pomógł: 239 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Artist » 2 maja 2009, o 19:02

1.
a)
Ukryta treść:    
b)
Ukryta treść:    

tomalla
Użytkownik
Użytkownik
Posty: 179
Rejestracja: 10 mar 2009, o 15:28
Płeć: Mężczyzna
Lokalizacja: Olsztyn
Podziękował: 2 razy
Pomógł: 29 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: tomalla » 2 maja 2009, o 19:40

Zrobiłem zadanko 4! Bardzo prosiłbym kogoś o sprawdzenie rozwiązania, to jest mój pierwszy tego typu przykład

\(\displaystyle{ 2^{1093}-2\equiv0(mod\ 1093^2)\qquad\Rightarrow\qquad 2^{1093}\equiv2(mod\ 1093)}\)

Z tw. Eulera mamy:

\(\displaystyle{ a^{\varphi (m)}\equiv 1(mod\ m)}\)

\(\displaystyle{ 2^{\varphi (1093)}\equiv 1(mod\ 1093)\qquad\Rightarrow\qquad 2^{1092}\equiv 1(mod\ 1093)}\)

Mnożąc to przez następującą kongruencję:

\(\displaystyle{ 2\equiv -1091(mod\ 1093)}\)

... otrzymujemy:

\(\displaystyle{ 2^{1093}\equiv-1091(mod\ 1093)}\)

Teraz od kongruencji na początku posta odjąłem tą ostatnią:

\(\displaystyle{ 0\equiv1093(mod\ 1093)}\)

... co oczywiście świadczy o tym, że liczba ta jest podzielna przez \(\displaystyle{ 1093^2}\).

I jak?
Ostatnio zmieniony 2 maja 2009, o 19:55 przez tomalla, łącznie zmieniany 1 raz.

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Dumel » 2 maja 2009, o 19:53

18. a)
z twierdzenia Wilsona \(\displaystyle{ 28! \equiv -1 (mod \ 29)}\)
ponadto \(\displaystyle{ (14!)^2 \equiv 1 \cdot 2 \cdot ... \cdot 14 \cdot (-28) \cdot (-27) \cdot ... \cdot (-15) \equiv 28! \equiv -1 \ (mod \ 29)}\)
\(\displaystyle{ NWD(29, 28!)=NWD(29, (14!)^2)=1}\) wiec kongruencje mozemy podzielic stronami co nam daje
\(\displaystyle{ {28 \choose 14} \equiv 1 \ (mod \ 29)}\)
---
tomalla pisze:Zrobiłem zadanko 4!
4!=24 a niestety są tylko 23 zadania...

tomalla
Użytkownik
Użytkownik
Posty: 179
Rejestracja: 10 mar 2009, o 15:28
Płeć: Mężczyzna
Lokalizacja: Olsztyn
Podziękował: 2 razy
Pomógł: 29 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: tomalla » 2 maja 2009, o 19:56

Zabawne, Dumel Zamiast się naśmiewać, powiedziałbyś czy dobrze obliczyłem

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Dumel » 2 maja 2009, o 19:57

chyba zapomniales ze trzeba rozstrzygnac podzielnosc przez \(\displaystyle{ 1093^2}\) a nie przez \(\displaystyle{ 1093}\).
chyba ze nie zapomniales ale wtedy tez jest zle bo oparles przeksztalcenia na implikacji a nie rownoważności

tomalla
Użytkownik
Użytkownik
Posty: 179
Rejestracja: 10 mar 2009, o 15:28
Płeć: Mężczyzna
Lokalizacja: Olsztyn
Podziękował: 2 razy
Pomógł: 29 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: tomalla » 2 maja 2009, o 20:00

Nie wiem, czy o to ci chodzi, ale końcówkę posta już zdążyłem poprawić przed tobą Jeżeli nie, to powiedz o jakim fragmencie mówisz.

frej

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: frej » 2 maja 2009, o 20:03

2. \(\displaystyle{ L \equiv (50^{56} + 34)^{28} \equiv (16+34)^{28} \equiv 70 \pmod{111}}\)

Chodzi o tę dziwną implikację na początku, która jest błędem.-- 2 maja 2009, 20:08 --16a) \(\displaystyle{ x^7 +x^3 +x +4}\)

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Dumel » 2 maja 2009, o 20:08

zad. 23.
zgodnie z twierdzeniem Wilsona \(\displaystyle{ p}\) jest liczbą pierwszą wtedy i tylko wtedy gdy \(\displaystyle{ (p-1)! \equiv -1 (mod \ p)}\) co jest rownowazne kongruencji \(\displaystyle{ (p-1)! \equiv p-1 (mod \ p)}\). liczby \(\displaystyle{ p}\) i \(\displaystyle{ p-1}\) są względnie pierwsze wiec dzieląc kongruencję stronami dostajemy \(\displaystyle{ (p-2)! \equiv 1(mod \ p)}\)

frej

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: frej » 2 maja 2009, o 20:12

16b) \(\displaystyle{ 8x^4 + 7x^3 + 8x^2 + 7x}\)

-- 2 maja 2009, 20:22 --

12.

\(\displaystyle{ \left( \frac{219}{383} \right)= \left( \frac{3}{383} \right) \left( \frac{73}{383} \right) = - \left( \frac{2}{3} \right) \left( \frac{18}{73} \right) = \left( \frac{3}{73} \right)^2 \left( \frac{2}{73} \right)= (-1)^\frac{73^2-1}{8}=1}\)

Czyli jest resztą kwadratową.

-- 2 maja 2009, 20:35 --

6. \(\displaystyle{ =3^3 \cdot 5^2 \cdot 11^2 \cdot 2999}\)-- 2 maja 2009, 20:39 --11a)

\(\displaystyle{ \sum_{i=1}^{\infty} \left[ \frac{5258}{5^i }\right] =1051+210+42+8 +1=1312}\)

Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Swistak » 2 maja 2009, o 20:55

tomalla pisze:Nie wiem, czy o to ci chodzi, ale końcówkę posta już zdążyłem poprawić przed tobą Jeżeli nie, to powiedz o jakim fragmencie mówisz.
Nie znam własności funkcji \(\displaystyle{ \varphi(n)}\) ani twierdzenia Eulera (tzn. no niby znam nawet 2, ale inne ), więc nie rozumiem rozwiązania zadania w całości, ale z tego co widzę, to udowodniłeś że \(\displaystyle{ x\equiv1093 (mod 1993)}\), a z tego wcale nie wynika, że dana liczba jest podzielna przez \(\displaystyle{ 1093^{2}}\).

tomalla
Użytkownik
Użytkownik
Posty: 179
Rejestracja: 10 mar 2009, o 15:28
Płeć: Mężczyzna
Lokalizacja: Olsztyn
Podziękował: 2 razy
Pomógł: 29 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: tomalla » 2 maja 2009, o 21:07

Na samym początku postu mam:

\(\displaystyle{ 2^{1093}-2\equiv0(mod\ 1093^2)\qquad\Rightarrow\qquad 2^{1093}\equiv2(mod\ 1093)}\)

Skoro

\(\displaystyle{ 2^{1093}\equiv2(mod\ 1093)}\)

jest prawdziwe, to

\(\displaystyle{ 2^{1093}-2\equiv0(mod\ 1093^2)}\)

także jest prawdziwe. Z logiki nie byłem nigdy dobry, więc jak to nie jest jednak prawdą, to ... napiszcie

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Dumel » 2 maja 2009, o 21:17

tomalla pisze:Na samym początku postu mam:
\(\displaystyle{ 2^{1093}-2\equiv0(mod\ 1093^2)\qquad\Rightarrow\qquad 2^{1093}\equiv2(mod\ 1093)}\)
to jest samo w sobie ok ale nic Ci tu nie daje i wprowadza Ciebie w błąd
tomalla pisze: Skoro
\(\displaystyle{ 2^{1093}\equiv2(mod\ 1093)}\)
jest prawdziwe, to
\(\displaystyle{ 2^{1093}-2\equiv0(mod\ 1093^2)}\)
także jest prawdziwe.
tu za to wykorzystujesz nieprawdziwą implikację
\(\displaystyle{ 2^{1093}\equiv2(mod\ 1093)\qquad\Rightarrow\qquad 2^{1093}-2\equiv0(mod\ 1093^2)}\)
inaczej nie potrafie tego wujaśnić (moze jeszcze tak: \(\displaystyle{ \Rightarrow \neq \Leftrightarrow}\)) Twój dowód to coś w stylu: \(\displaystyle{ 4|2 \Rightarrow 2|2}\) a teraz \(\displaystyle{ 2|2 \Rightarrow 4|2}\) cnd

tomalla
Użytkownik
Użytkownik
Posty: 179
Rejestracja: 10 mar 2009, o 15:28
Płeć: Mężczyzna
Lokalizacja: Olsztyn
Podziękował: 2 razy
Pomógł: 29 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: tomalla » 2 maja 2009, o 21:42

Możliwe, że coś pokręciłem

Jak to jest z zasadą:

\(\displaystyle{ a\equiv b(mod\ m)}\)

i:

\(\displaystyle{ d|m}\)

to:

\(\displaystyle{ a\equiv b(mod\ d)}\)

Rozumiem, że źle to zinterpretowałem, tak? Tutaj jest błąd?

Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[MIX][Teoria liczb] Zestaw od Iwana

Post autor: Dumel » 2 maja 2009, o 22:05

to prawda, ale implikacja w drugą stronę jest fałszywa
(ale śmietnik już sie w tym temacie zrobił)

ODPOWIEDZ