(2 zadania) NWD i liczby pierwsze

[aniczka]

mam problem z kilkoma zadaniami i prosze o pomoc

zad.1
wykazac ze jezeli liczby \(\displaystyle{ a,b}\) sa wzglednie pierwsze to \(\displaystyle{ NWD(11a+2b,18a+5b)=1}\) lub \(\displaystyle{ 19}\)

zad.2
pokazac ze jesli \(\displaystyle{ p,q}\) sa liczbami pierwszymi \(\displaystyle{ >3}\), to liczba \(\displaystyle{ p^2-q^2}\) jest podzielna przez \(\displaystyle{ 24}\).

[gnicz]

Zadanie II

Wszystkie liczby pierwsze wieksze od \(\displaystyle{ 3}\) mozna przedstawic w postaci:
\(\displaystyle{ 6k \pm 1}\)

tak wiec:
\(\displaystyle{ p = 6a \pm 1\\
q = 6b\pm 1}\)

Zakladamy ze:
\(\displaystyle{ p = 6a + b\\
q = 6c + d}\)

gdzie: \(\displaystyle{ a, c \in\NN; b, d\in \{-1; 1\}}\)

\(\displaystyle{ p^2 - q^2 = (p - q)(p + q) = (6a + b - 6c - d)(6a + b + 6c + d) =\\=(6a - 6c + b - d)(6a + 6c + b + d)}\)

Mamy cztery przypadki:
a) \(\displaystyle{ b = -1; d = -1}\)

\(\displaystyle{ p^2 - q^2 = (6a - 6c - 1 + 1)(6a + 6c - 1 - 1) = (6a - 6c)(6a + 6c - 2) =\\=12(a - c)(3a + 3c - 1)}\)

Gdy: \(\displaystyle{ 24\mid 12(a - c)(3a + 3c - 1) 2|(a - c)(3a + 3c - 1)}\). Mamy:

\(\displaystyle{ 2\mid a \land 2\mid b \Rightarrow 2\mid (a - c)\\
(2\nmid a \land 2\mid b) \lor (2\mid a \land 2\nmid b) \Rightarrow 2\mid (3a + 3c - 1)\\
2\nmid a \land 2\nmid b \Rightarrow 2\mid (a - c)}\)

b) \(\displaystyle{ b = 1; d = -1}\)

\(\displaystyle{ p^2 - q^2 = (6a - 6c + 1 + 1)(6a + 6c + 1 - 1) = (6a - 6c + 2)(6a + 6c) =\\=12(3a - 3c + 1)(a + c)}\)

Sytuacja analogiczna jak poprzednio.

c) \(\displaystyle{ b = -1; d = 1}\)

\(\displaystyle{ p^2 - q^2 = (6a - 6c - 1 - 1)(6a + 6c - 1 + 1) = (6a - 6c - 2)(6a + 6c) =\\=12(3a - 3c - 1)(a + c)}\)

Podobnie jak poprzednio.

d) \(\displaystyle{ b = 1; d = 1}\)

\(\displaystyle{ p^2\mbox{ i }q^2 = (6a - 6c + 1 - 1)(6a + 6c + 1 + 1) =(6a - 6c)(6a + 6c + 2) =\\= 12(a - c)(3a + 3c + 1)}\)

Takze identyczna sytuacja.

Pozdrawiam, GNicz

[Yavien]

zadanie I nie jest prawdziwe:
\(\displaystyle{ a= 19\\
b = 13}\)

\(\displaystyle{ NWD(11a+2b,18a+5b)=NWD(407,1023)= 11}\)

[gnicz]

Dla podanych przez Ciebie wartosci:

\(\displaystyle{ a = 19\\
b = 13}\)

\(\displaystyle{ 11a + 2b = 11 \cdot 19 + 2 \cdot 13 = 235\\
18a + 5b = 18 \cdot 19 + 5 \cdot 13 = 407}\)

\(\displaystyle{ NWD(235, 407) = 1}\)

Pozdrawiam, GNicz

[Yavien]

faktycznie, cos zle wyliczylam. W takim razie to moze byc prawda, ale teoria liczb jest troszke jaby zapomniana przeze mnie, bede musiala pomyslec nad rozwiazaniem.

[TomciO]

zad.2

Latwo zauwazyc, ze reszty z dzielenia liczb pierwszych przez \(\displaystyle{ 8}\) wynosza \(\displaystyle{ 1}\) albo \(\displaystyle{ 3}\) albo \(\displaystyle{ 5}\) albo \(\displaystyle{ 7}\).
Latwo rowniez zauwazyc, ze reszta z dzielenia liczb pierwszych przez \(\displaystyle{ 3}\) wynosi \(\displaystyle{ 1}\) albo \(\displaystyle{ 2}\).
Wiec dla \(\displaystyle{ 8}\) mamy reszty: \(\displaystyle{ 1,3,5,7}\)
Dla 3: \(\displaystyle{ 1,2}\)
Potegujac liczbe poteguje sie rowniez reszta z dzielenia, a wiec:
\(\displaystyle{ 1 \cdot 1=1\\
3 \cdot 3=9\\
5 \cdot 5=25\\
7 \cdot 7=49}\)
Kazda z tych liczb mozna zapisac w postaci \(\displaystyle{ 8k+1}\), czyli kazda liczba pierwsza \(\displaystyle{ >3}\) podniesiona do kwadratu przy dzieleniu przez \(\displaystyle{ 8}\) daje reszte \(\displaystyle{ 1}\).
Robimy to samo z resztami dla \(\displaystyle{ 3}\):
\(\displaystyle{ 1 \cdot 1=1\\
2 \cdot 2=4}\)
Tutaj rowniez kazda z tych liczb mozna zapisac w postaci \(\displaystyle{ 3k+1}\), a wiec widac ze kazda liczba pierwsza \(\displaystyle{ >3}\) podniesiona do kwadratu przy dzieleniu przez \(\displaystyle{ 3}\) daje reszte \(\displaystyle{ 1}\).
Wynika z tego, ze kazda liczba pierwsza \(\displaystyle{ >3}\) podniesiona do kwadratu przy dzieleniu przez \(\displaystyle{ 24}\) daje reszte \(\displaystyle{ 1}\) (bo \(\displaystyle{ 8 \cdot 3=24}\)). Stad wiadomo, ze roznica dwoch liczb pierwszych \(\displaystyle{ >3}\) podniesionych do kwadratow jest podzielna przez \(\displaystyle{ 24}\) gdyz maja ta sama reszte z dzielenia przez \(\displaystyle{ 24}\).

Slabo to wytlumaczylem, ale robilem co moglem :.

[Gregsky]

Wszystkie liczby pierwsze wieksze od \(\displaystyle{ 3}\) mozna przedstawic w postaci:
\(\displaystyle{ 6k \pm 1}\)

Skąd ty to wziąłeś?Jest na to jakiś dowód? To że niektóre liczby pierwsze pasują, to nie znaczy ze wszystkie...

[półpasiec]

zalozmy przeciwnie, \(\displaystyle{ p=6k+2=2(3k+1)}\) nie
itd z reszta

[gnicz]

Skąd ty to wziąłeś? Jest na to jakiś dowód? To że niektóre liczby pierwsze pasują, to nie znaczy ze wszystkie...

Teoria liczb sie klania.

Pozdrawiam, GNicz

[półpasiec]

niech \(\displaystyle{ d}\) bedzie \(\displaystyle{ (11a+2b,18a+5b)}\) wtedy
\(\displaystyle{ d\mid 2(11a+2b)+3(18a+5b)=19(4a+b)}\)
oraz
\(\displaystyle{ d\mid 5(11a+2b)-2(18a+5b)=19a}\)
zalozmy przeciwnie, ze nwd jest rozny od \(\displaystyle{ 1}\) albo \(\displaystyle{ 19}\) wtedy dzieli \(\displaystyle{ 4a+b}\) oraz \(\displaystyle{ a}\), ale wtedy dzielilby tez \(\displaystyle{ b}\). sprzecznosc

[Poszukujaca]

Odświeżę stary temat, ale właśnie trafiłam na to zadanko i mi się bardzo spodobało

Pojawiło mi się w głowie pytanie co do rozwiązania zaproponowanego przez TomciO.

Twierdzimy, że każda liczba pierwsza podniesiona do kwadratu (większa od 3) daje się przedstawić w postaci \(\displaystyle{ 8k+1}\). I podobnie każda liczba pierwsza podniesiona do kwadratu (większa od 3) daje się przedstawić w postaci \(\displaystyle{ 3k+1}\).
Ok, rozumiem to.

Ale dlaczego potem twierdzimy, że takie liczby przy dzieleniu przez 24 dają resztę 1? Tego przejścia nie rozumiem i proszę o objaśnienie.

[Santiago A]

Chińskie twierdzenie o resztach.

[dec1]

Mamy \(\displaystyle{ p^2=8k+1=3l+1}\) dla jakichś całkowitych \(\displaystyle{ k, l}\)

Stąd \(\displaystyle{ 8k=3l}\), a ponieważ \(\displaystyle{ \mathrm{NWD}(8,3)=1}\), mamy \(\displaystyle{ 3\mid k}\) oraz \(\displaystyle{ 8\mid l}\)

Stąd \(\displaystyle{ p^2=24m+1}\) dla \(\displaystyle{ m=\frac{k}{3}=\frac{l}{8}}\)

[Poszukujaca]

Dziękuję, teraz juź wszystko jasne