Zadania na kolokwium

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
maniekVeB
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 25 sty 2012, o 15:21
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

Zadania na kolokwium

Post autor: maniekVeB »

1. Rozwiąż kongurencje
\(\displaystyle{ a) x^{287} \equiv 3 (mod 8)

b) 28x^{236}+14x^{21}-34x^{13}+5 \equiv 0 (mod 15)

c) 5x \equiv -7 (mod 12)}\)

2. Wyznaczyć wszystkie rozwiązania w liczbach naturalnych
\(\displaystyle{ x^{2}-7y^{2}=1}\)

3. Pokazać, że równanie nie ma rozwiązań
\(\displaystyle{ 15x^{2}+7y^{2}=6}\)

4. Wyznaczyć cyfry a i b tak, aby liczba była podzielna przez 36
\(\displaystyle{ 27a3714b}\)

5. Znaleźć wszystkie rozwiązania równania diofantycznego
\(\displaystyle{ 64x^{2}-y^{2}=488}\)
Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 612 razy

Zadania na kolokwium

Post autor: Vax »

1a) Zauważ, że x nie może być parzyste, czyli \(\displaystyle{ (x,8)=1}\) więc z twierdzenia Eulera \(\displaystyle{ x^4 \equiv 1 \pmod{8} \Rightarrow x^{287} \equiv x^3 \equiv 3\pmod{8}}\) skąd łatwo dostajemy \(\displaystyle{ x\equiv 3 \pmod{8}}\)

1b) Z Chińskiego twierdzenia o resztach mamy:

\(\displaystyle{ 28x^{236}+14x^{21}-34x^{13}+5 \equiv 0\pmod{15} \\ \\ \iff \\ \\ \begin{cases} 28x^{236}+14x^{21}-34x^{13}+5 \equiv 0\pmod{3}\\ 28x^{236}+14x^{21}-34x^{13}+5 \equiv 0\pmod{5} \end{cases}}\)

Zajmijmy się pierwszą kongruencją, \(\displaystyle{ 28x^{236}+14x^{21}-34x^{13}+5 \equiv 0\pmod{3} \Leftrightarrow x^{236}+2x^{21}+2x^{13}+2 \equiv 0\pmod{3}}\), widzimy teraz, że x nie może być podzielne przez 3, czyli z Twierdzenia Eulera \(\displaystyle{ x^2 \equiv 1\pmod{3}}\) więc nasza kongruencja jest równoważna \(\displaystyle{ 1+2x+2x+2 \equiv 0\pmod{3} \Leftrightarrow x\equiv 0\pmod{3}}\)

Teraz druga kongruencja, jest ona równoważna \(\displaystyle{ 3x^{236}+4x^{21}+x^{13} \equiv 0\pmod{5}}\), działa ona jeżeli \(\displaystyle{ x\equiv 0\pmod{5}}\), załóżmy, że 5 nie dzieli x, wtedy z tw. Eulera \(\displaystyle{ x^4 \equiv 1\pmod{5}}\) i jest ona równoważna \(\displaystyle{ 3+4x+x \equiv 0\pmod{5} \Leftrightarrow 3\equiv 0\pmod{5}}\) sprzeczność, czyli musi być:

\(\displaystyle{ \begin{cases} x \equiv 0\pmod{3}\\ x \equiv 0\pmod{5} \end{cases} \Leftrightarrow x\equiv 0\pmod{15}}\) jednak bezpośrednio wstawiając do naszego wyjściowego równania dostajemy \(\displaystyle{ 5 \equiv 0\pmod{15}}\) sprzeczność, więc dana kongruencja nie ma rozwiązań.

1c) \(\displaystyle{ 5x \equiv -7 \equiv 5\pmod{12}/:5 \Leftrightarrow x\equiv 1\pmod{12}}\)

2) Poczytaj o równaniu Pella.

3) Rozpatrując dane równanie mod 5 widzimy, że \(\displaystyle{ 7y^2 \equiv 6\pmod{5} \Leftrightarrow 2y^2 \equiv 1\pmod{5}/\cdot 3 \Leftrightarrow y^2 \equiv 3\pmod{5}}\) sprzeczność, bo 3 jest nieresztą kwadratową mod 5.

4) Dana liczba w szczególności ma się dzielić przez 9, więc \(\displaystyle{ 9 | 2+7+a+3+7+1+4+b \Leftrightarrow 9 | a+b+6}\) ale \(\displaystyle{ a+b \le 18}\) więc może być jedynie \(\displaystyle{ a+b+6 = 9 \vee a+b+6=18 \Leftrightarrow a+b=3 (*)\vee a+b=12(**)}\)

Dana liczba ma się również dzielić przez 4, czyli może być jedynie \(\displaystyle{ b=0 \vee b=4 \vee b=8}\), w 1 przypadku z \(\displaystyle{ (*)}\) dostajemy \(\displaystyle{ (a,b)=(3,0)}\), \(\displaystyle{ (**)}\) nie daje rozwiązań, w przypadku \(\displaystyle{ b=4}\) \(\displaystyle{ (*)}\) nie daje rozwiązań a z \(\displaystyle{ (**)}\) dostajemy \(\displaystyle{ (a,b) = (8,4)}\) a w przypadku \(\displaystyle{ b=8}\) \(\displaystyle{ (*)}\) nie daje rozwiązań, a z \(\displaystyle{ (**)}\) mamy \(\displaystyle{ (a,b) = (4,8)}\) czyli tezę spełniają liczby \(\displaystyle{ 27337140 \vee 27837144 \vee 27437148}\)

5) \(\displaystyle{ (8x-y)(8x+y)=488}\) i teraz parę przypadków.
ODPOWIEDZ