Kilka (prostych?) zadań z teorii liczb...

[MiErOn]

Witam!

Przygotowuje się do bardzo ważnego dla mnie egzaminu... Mam na to parę dni (dokładnie 4 ??: ) i chciałbym sie dowiedzieć, czy można, a jeżeli można, to jak prosto i szybko można rozwiązać tego typu zadania:


1. Znaleźć liczby całkowite, które przy dzieleniu przez 4 dają resztę 1, a przy dzieleniu przez 5 dają resztę 0. Jakie reszty dają te liczby przy dzieleniu przez 40?

2. Sprawdzić, czy...

\(\displaystyle{ 3^{91}+9^{91}+1\equiv 0(mod \ 13)}\)

3. Niech \(\displaystyle{ \varphi}\) oznacza funkcję Eulera. Znaleźć a, jeżeli \(\displaystyle{ a=p\cdot q^{2}}\), gdzie p, q są różymi między sobą

liczbami pierwszymi oraz \(\displaystyle{ \varphi (a) =40}\) , \(\displaystyle{ p-q=2}\)

4. Niech \(\displaystyle{ a,b \mathbb{N}}\) i niech \(\displaystyle{ 17a=31b}\). Czy liczba \(\displaystyle{ a-b}\) jest złożona?

5. Dla jakiej wartości parametru \(\displaystyle{ \lambda}\) równanie...

\(\displaystyle{ 279x+372y=\lambda}\)

posiada rozwiązanie w liczbach całkowitych?

6. Rozwiązać kongurencje:

\(\displaystyle{ 5x^{2}-15x+22\equiv 0(mod \ 6)}\)

7. Niech \(\displaystyle{ \varphi}\) oznacza funkcję Eulera oraz \(\displaystyle{ n \mathbb{N}}\). Sprawdzić, czy \(\displaystyle{ \varphi (4n+2)=\varphi (2n+1)}\)

8. Czy liczbę \(\displaystyle{ 5050505}\) można zapisać jako sumę dwóch liczb pierwszych?

9. Czy dla dowolnej liczby naturalnej n zachodzi kongruencja:

\(\displaystyle{ 7^{4n+1}+3^{4n+2}+4\equiv 0(mod \ 10)}\)?

10. Ile jest liczb naturalnych w przedziale \(\displaystyle{ [1,120]}\), które nie są względnie pierwsze z 30?

11. Pokazać, że jeżeli n jest liczbą nieparzystą, to \(\displaystyle{ n^{2}-1\equiv 0(mod \ 8)}\)

12. Jakie liczby między 2320 i 2350 są pierwsze?

13. Znaleźć liczbę pierwszą p, jeżeli wiadomo, że \(\displaystyle{ 4p^{2}+1}\) oraz \(\displaystyle{ 6p^{2}+1}\) są liczbami pierwszymi

14. Rozwiązać w liczbach całkowitych równanie: \(\displaystyle{ 8x+11y-19z=62}\)

15. Rozwiązać w liczbach naturalnych układ równań:

\(\displaystyle{ \begin{cases} 2x-3y+2z=23\\3x-2y+z=5\end{cases}}\)

Z góry dziękuje za odpowiedź. Bardzo mi na tym zalezy... Wszelkie rady, wskazówki, triki będa mi ogromnie pomocne

[Tristan]

Ad 7:
Zauważ, że \(\displaystyle{ \varphi ( 4n+2)= \varphi ( 2(2n+1) )= \varphi ( 2) \varphi(2n+1)=\varphi (2n+1)}\), ponieważ \(\displaystyle{ NWD( 2, 2n+1)=1}\).

[mol_ksiazkowy]

ad11
\(\displaystyle{ n=2k+1, \ n^2-1 =(n-1)(n+1)=2k(2k+2)=4k(k+1)}\)

[ Dodano: 11 Września 2007, 19:54 ]
ad 8
nie , bo jesli 5050505=p+q , to p=2 (lub q=2), ale q=5050503
dzieli sie przez 3

[ Dodano: 11 Września 2007, 19:59 ]
ad 4
17 i 31 to l. pierwsze wiec a musi dzielic 31, zas b musi dzielic 17
tj a=31x
b=17 y
wtedy wstawiamy i x=y, tj a-b = 14x l zlozona
(bo podzielna np przez 7)

[ Dodano: 11 Września 2007, 20:01 ]
ad2 wsk
\(\displaystyle{ 3^3 \equiv 1 \ ( mod \ 13)}\)

[ Dodano: 11 Września 2007, 20:05 ]
ad 5
wkw aby rownanie
ax+by =c
miało rozw w w l. całkowitych
jest aby c było podzielne przez NWD(a,b)

tj lambda musi byc podzielne przez NWD(279, 372)

[ Dodano: 11 Września 2007, 20:38 ]

ad 15
mnozymy drugie rownanie przez 2 i odejmujemy od pierwszego i uzyskamy
\(\displaystyle{ y=4x+13}\)
Po wstaw do ..np drugiego bedzie z policzone
\(\displaystyle{ z =5x+31}\)

rozw stanowi kazda trójka postaci
\(\displaystyle{ (x, 4x+13, 5x+31)}\) gdzie \(\displaystyle{ x N}\)
Besposrednim rachunkiem sprawdzamy ze tak jest istotnie

[max]

Czy w 3. nie powinno być przypadkiem: \(\displaystyle{ a = p^{2}\cdot q}\) albo \(\displaystyle{ q - p = 2}\)?
Jeśli nie, to:
\(\displaystyle{ \varphi ( a) = \varphi ( p\cdot q^{2}) =\varphi ( p) \varphi ( q^{2}) = (p - 1)\cdot q\cdot (q - 1) = (q + 1)\cdot q\cdot (q - 1) = 40}\)
i równanie nie ma rozwiązań w liczbach naturalnych.

Ad 9:
Zauważ, że:
\(\displaystyle{ 7^{4}\equiv 1 od{10}\\
3^{4}\equiv 1 od{10}}\)

[MiErOn]

Czy w 3. nie powinno być przypadkiem: \(\displaystyle{ a = p^{2}\cdot q}\) albo \(\displaystyle{ q - p = 2}\)?

Nie raczej nie... tak jak napisałem taka jest treść... Wydaje mi sie jednak, że powinno byc rozwiązanie... Nie da rady inaczej tego próbować? ... Bo np. mam podobne zadanie:

Funkcja Eulera dla argumentu a przyjmuje wartość 11424, \(\displaystyle{ a=p^{2}q^{2}}\) , przy czym p i q są dwiema różnymi miedzy sobą liczbami pierwszymi. Znaleźć liczbę a.

i tutaj nie możemy wykorzystać podstawienia pod jedną zmienną z warunku \(\displaystyle{ p-q=2}\). Dojdziemy do \(\displaystyle{ p\cdot (p-1)\cdot q\cdot (q-1)}\). Co wtedy?

ad11
\(\displaystyle{ n=2k+1, \ n^2-1 =(n-1)(n+1)=2k(2k+2)=4k(k+1)}\)

a czy mógłbyś mi to jakoś słownie wytłumaczyć, żebym zrozumiał istotę zadania?

ad 8
nie , bo jesli 5050505=p+q , to p=2 (lub q=2), ale q=5050503
dzieli sie przez 3

Czy sprawdzenie dla jednej liczby pierwszej 2 wystarczy aby tak stwierdzić? Bo przecież p może być jakąś wyższą liczbą pierwszą jak 2, a q mniejszą jak 5050503... Jest tyle możliwości... Czy to nie ma znaczenia?

ad 4
17 i 31 to l. pierwsze wiec a musi dzielic 31, zas b musi dzielic 17
tj a=31x
b=17 y
wtedy wstawiamy i x=y, tj a-b = 14x l zlozona
(bo podzielna np przez 7)

ok, zrozumiałem zadanie

\(\displaystyle{ 3^3 \equiv 1 \ ( mod \ 13)}\)

Cieżko mi załapać te kongruencje mimo wskazówek... :/

Zauważ, że:
\(\displaystyle{ 7^{4}\equiv 1 od{10}\\ 3^{4}\equiv 1 od{10}}\)

Jak wyżej... choć tutaj trochę więcej widzę

ad 5
wkw aby rownanie
ax+by =c
miało rozw w w l. całkowitych
jest aby c było podzielne przez NWD(a,b)

tj lambda musi byc podzielne przez NWD(279, 372)

Rozumiem

ad 15
mnozymy drugie rownanie przez 2 i odejmujemy od pierwszego i uzyskamy (...)

To także zrozumiałem, dzięki

Ad 7:
Zauważ, że \(\displaystyle{ \varphi ( 4n+2)= \varphi ( 2(2n+1) )= \varphi ( 2) \varphi(2n+1)=\varphi (2n+1)}\) , ponieważ \(\displaystyle{ NWD( 2, 2n+1)=1}\) .

Czyli postepując analogicznie gdybym miał np. sprawdzić równanie \(\displaystyle{ \varphi (6n+3)=\varphi(2n+1)}\) otrzymujemy \(\displaystyle{ \varphi ( 6n+3)= \varphi ( 3(2n+1) )= \varphi ( 3) \varphi(2n+1)}\) i to w tym wypadku nie równa się \(\displaystyle{ (2n+1)}\) zgadza się?

[PFloyd]

ad 8
jedna z liczb pierwszych musi być parzysta żeby suma była nieparzysta

ad 2
\(\displaystyle{ 3^3=27\equiv 1(mod13)\\
(3^3)^{27}\equiv 1^{27}(mod13)\\
\\
9^3=729\equiv 1(mod13)\\
(9^3)^{27}\equiv 1(mod13)\\
\\
3^{91}+9^{27}+1\equiv 3(mod13)}\) (spróbuj teraz zrobić 9)

ad 11

\(\displaystyle{ (2k+1)^2-1=4k^2+4k=4k(k+1)}\) dla dowolnego całkowitego k
gdy k jest parzyste (2p), mamy \(\displaystyle{ 8p(2p+1)\equiv 0(mod8)}\)
gdy nieparzyste (2p+1), to \(\displaystyle{ 4(2p+1)(2p+2)=8(2p+1)(p+1)\equiv 0 (mod8)}\)

[mol_ksiazkowy]

ad1 1. Znaleźć liczby całkowite, które przy dzieleniu przez 4 dają resztę 1, a przy dzieleniu przez 5 dają resztę 0. Jakie reszty dają te liczby przy dzieleniu przez 40?

Cóz tutaj łatwo widac ze ta postac to \(\displaystyle{ x=20k+5}\), k=0,1,2,...... zas jaka rezste x da przy dzieleniu przez 40 ?
gdy k parzyste reszta =5
gdy k nieparzyste reszta =25

Mysle ze szczegoly dopracujesz
cdn....

[ Dodano: 11 Września 2007, 22:51 ]
MiEron napisał

Czy sprawdzenie dla jednej liczby pierwszej 2 wystarczy aby tak stwierdzić? Bo przecież p może być jakąś wyższą liczbą pierwszą jak 2, a q mniejszą jak 5050503... Jest tyle możliwości... Czy to nie ma znaczenia?

Jesli obie beda wieksze od 2 to bede nieparzyste, a ich suma parzysta, tj rózna od 5050505

[max]

Czy w 3. nie powinno być przypadkiem: \(\displaystyle{ a = p^{2}\cdot q}\) albo \(\displaystyle{ q - p = 2}\)?

Nie raczej nie... tak jak napisałem taka jest treść... Wydaje mi sie jednak, że powinno byc rozwiązanie... Nie da rady inaczej tego próbować? ... Bo np. mam podobne zadanie:

Funkcja Eulera dla argumentu a przyjmuje wartość 11424, \(\displaystyle{ a=p^{2}q^{2}}\) , przy czym p i q są dwiema różnymi miedzy sobą liczbami pierwszymi. Znaleźć liczbę a.

i tutaj nie możemy wykorzystać podstawienia pod jedną zmienną z warunku \(\displaystyle{ p-q=2}\). Dojdziemy do \(\displaystyle{ p\cdot (p-1)\cdot q\cdot (q-1)}\). Co wtedy?

W tym wypadku chyba nietrudno rozłożyć 11424 na czynniki pierwsze:
\(\displaystyle{ 11424 = 2^{5}\cdot 3\cdot 7\cdot 17}\)
i zauważyć, że:
\(\displaystyle{ 2^{5}\cdot 3\cdot 7\cdot 17 = 6\cdot 7\cdot 16\cdot 17}\)
stąd szukana liczba to:
\(\displaystyle{ 7^{2}\cdot 17^{2} = 49\cdot 289 =14161}\)

Co do kongruencji, to pamiętaj, że możemy obie strony kongruencji pomnożyć przez stałą (całkowitą), podnieść do potęgi naturalnej, a kongruencje o tym samym module możemy dodawać stronami.

[Tristan]

Ad 7:
Nie, ze względu na fakt, że np. dla \(\displaystyle{ n=4}\) masz \(\displaystyle{ NWD(3, 2 \cdot 4 +1)=NWD(3,9)=3>1}\). A dla dowolnego naturalnego n mamy, że liczba postaci \(\displaystyle{ 2n+1}\) jest nieparzysta, więc nie ma wspólnego dzielnika z dwójką, więc \(\displaystyle{ NWD(2, 2n+1)=1}\).

[Piotr Rutkowski]

ad6: Rozpatrz sobie po protu wszystkie możliwości (tak jest najłatwiej). Wyjdzie Ci wynik:
\(\displaystyle{ x \equiv 1 2 -1 -2}\)

[mol_ksiazkowy]

14. Rozwiązać w liczbach całkowitych równanie: \(\displaystyle{ 8x+11y-19z=62}\)

Budujemy dwa równania:
1) \(\displaystyle{ \ \ -19z+ t=62}\)
2) \(\displaystyle{ \ \ 8x+11y=t}\)

Kładziemy \(\displaystyle{ z=u}\), jak idzie o drugie to
rozw są postaci :
\(\displaystyle{ x= -4t +11v}\)
\(\displaystyle{ y= 3t -8v}\)

Dalej ...skoro, \(\displaystyle{ t=62+19u}\) to po
podst. dostanie sie. ze

\(\displaystyle{ x= -248 -76u +11v}\)
\(\displaystyle{ y= 186 +57u -8v}\)
\(\displaystyle{ z= u}\)
gdzie
\(\displaystyle{ u, v Z}\)


[ Dodano: 12 Września 2007, 03:07 ]

ad 9 wsk
\(\displaystyle{ 7^2 \equiv -1 \ (mod \ 10)}\)
\(\displaystyle{ 3^2 \equiv -1 \ (mod \ 10)}\)


[ Dodano: 12 Września 2007, 03:20 ]

o sorki to juz max podał...

[ Dodano: 12 Września 2007, 11:21 ]
ad 13


Przypadki p=2 i p=5 sprawdzasz osobnao...dalej widac, ze jakakolwiek cyfra konczy sie p: 1, 3, 7, 9, to i tak : \(\displaystyle{ (4p^2+1)(6p^2+1)=24p^4+10p^2+1}\) jest podzielne przez 5, a przecie"
\(\displaystyle{ 4p^2+1 5 6p^2+1}\)


[ Dodano: 12 Września 2007, 17:27 ]

ad 10
W sumie mozna policzyc ile jest tych wzglednie pierwszych z 30, taka
liczba musi miec rozklad na czynniki :
\(\displaystyle{ z= 7^a 11^b 13^c .....}\)

i w efekcie
b, c,.... sa równe 0 kub 1.

tj beda to l. pierwsze
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
73, 79, 83, 89, 97, 101, 103, 107, 109, 113

dojda tez cztery wielokrotnosci siodemki":
49, 77, 119, 91

oraz
1

Razem : 32

czyli wynik 120-32=88

[MiErOn]

Ad 9:
Zauważ, że:
\(\displaystyle{ 7^{4}\equiv 1 od{10}\\ 3^{4}\equiv 1 od{10}}\)

Ok skoro mamy, że

\(\displaystyle{ 7^{4}\equiv 1 od{10}\\ 3^{4}\equiv 1 od{10}}\)

to dalej...

\(\displaystyle{ 7^{4n+1}+3^{4n+2}+4\equiv 0 od{10}}\)
\(\displaystyle{ 7^{4n}\cdot 7+3^{4n}\cdot 3^{2}+4\equiv 0 od{10}}\)
\(\displaystyle{ (7^{4})^{n}\cdot 7+(3^{4})^{n}\cdot 3^{2}+4\equiv 0 od{10}}\)
\(\displaystyle{ (7^{4})^{n}\cdot 7+(3^{4})^{n}\cdot 9+4\equiv 0 od{10}}\)

I na tym można już zakończyć, czy jeszcze coś z tym robić?

Cóz tutaj łatwo widac ze ta postac to \(\displaystyle{ x=20k+5, k=0,1,2}\)

A jakby nie było jasno widać tego związku, to jak do niego dojść? Pytam przyszłościowo gdyby natrafiło się na trudniejsze liczby...

ad6: Rozpatrz sobie po protu wszystkie możliwości (tak jest najłatwiej). Wyjdzie Ci wynik:
\(\displaystyle{ x \equiv 1 2 -1 -2 }\)

Wiem, ze tak można... robiłem tak, ale zawsze po takim sposobie i podaniu wyniku tak, jak Ty mi podałeś, zawsze się mnie pytali: "No dobra, ale co z tym dalej?" Więc nie wiem co dalej robić i dlatego pytam czy jest na to jakiś inny, łatwiejszy sposób? ...

Budujemy dwa równania:
1) \(\displaystyle{ \ \ -19z+ t=62}\)
2) \(\displaystyle{ \ \ 8x+11y=t}\)

Czy możesz sprawdzić, czy dobrze zrozumiałem... na tym przykładzie \(\displaystyle{ 7x+15y-22z=29}\) ?

Dwa równania:
\(\displaystyle{ -22z+t=29}\)
\(\displaystyle{ 7x+15y=t}\)

\(\displaystyle{ z=u}\)

rozwiązania drugiego równania:
\(\displaystyle{ x=-2t+15v}\)
\(\displaystyle{ y=t+7v}\)

i ostateczny wynik
\(\displaystyle{ x=-58-44u+15v}\)
\(\displaystyle{ y=29+22u+7v}\)
\(\displaystyle{ z=u}\)

Dobrze?

Przypadki p=2 i p=5 sprawdzasz osobnao...dalej widac, ze jakakolwiek cyfra konczy sie p: 1, 3, 7, 9, to i tak : \(\displaystyle{ (4p^2+1)(6p^2+1)=24p^4+10p^2+1}\) jest podzielne przez 5, a przecie"
\(\displaystyle{ 4p^2+1 5 6p^2+1}\)

A dlaczego akurat przypadki \(\displaystyle{ p=2}\) oraz \(\displaystyle{ p=5}\) sprawdza się osobno i czemu badamy akurat iloczyn tych dwóch wyrażeń?

[mol_ksiazkowy]

MiEron napisał"

A jakby nie było jasno widać tego związku, to jak do niego dojść? Pytam przyszłościowo gdyby natrafiło się na trudniejsze liczby...

\(\displaystyle{ x=4*5k +r}\) skoro x dziel i sie przez 5 to \(\displaystyle{ r \{0, 5, 10, 15\}}\), a skoro x-1 dzieli sie przez 4 to r=5.

Czy możesz sprawdzić, czy dobrze zrozumiałem... na tym przykładzie \(\displaystyle{ 7x+15y-22z=29}\) ?

jest ok, Tylko w y mała pomyłka \(\displaystyle{ y=t-7v}\)
ale metode dobrze uzywasz!!

A dlaczego akurat przypadki \(\displaystyle{ p=2}\) oraz \(\displaystyle{ p=5}\) sprawdza się osobno

bo sa wyjatkowe, jesli p jest l. pierwsza, to
p=2
albo
p=5
albo
p w zapisie dziesietnym konczy sie pewna z tych cyfr 1, 3, 7, 9

[max]

Ad 9:
Zauważ, że:
\(\displaystyle{ 7^{4}\equiv 1 \pmod{10}\\ 3^{4}\equiv 1 \pmod{10}}\)

Ok skoro mamy, że

\(\displaystyle{ 7^{4}\equiv 1 \pmod{10}\\ 3^{4}\equiv 1 \pmod{10}}\)

to dalej...

\(\displaystyle{ 7^{4n+1}+3^{4n+2}+4\equiv 0 \pmod{10}}\)
\(\displaystyle{ 7^{4n}\cdot 7+3^{4n}\cdot 3^{2}+4\equiv 0 \pmod{10}}\)
\(\displaystyle{ (7^{4})^{n}\cdot 7+(3^{4})^{n}\cdot 3^{2}+4\equiv 0 \pmod{10}}\)
\(\displaystyle{ (7^{4})^{n}\cdot 7+(3^{4})^{n}\cdot 9+4\equiv 0 \pmod{10}}\)

Ponieważ przeprowadzasz dowód niejako 'od końca', to wypadałoby przed tym ciągiem przekształceń - żeby nikt Ci nie zarzucił, że zakładasz to, co masz udowodnić - dopisać, że przekształcasz tezę na równoważne i zakończyć stwierdzeniem, iż ostatnia kongruencja jest na mocy uwag poczynionych na wstępie prawdziwa, zatem prawdziwa jest również równoważna wyjściowa postać tej kongruencji, co kończy dowód.

...a można też robić 'w drugą stronę', tzn poprzekształcać:
\(\displaystyle{ 7^{4}\equiv 1 \pmod{10}\\ 3^{4}\equiv 1 \pmod{10}}\)
tak, aby otrzymać tezę - wtedy dowód wymagałby mniej dodatkowych uwag.

[MiErOn]

ad 5
wkw aby rownanie
ax+by =c
miało rozw w w l. całkowitych
jest aby c było podzielne przez NWD(a,b)

tj lambda musi byc podzielne przez NWD(279, 372)

Upewnienie: Tutaj wyjdzie \(\displaystyle{ \lambda =93}\) , czy też może \(\displaystyle{ \lambda =93k}\), gdzie k=1,2,3,... ?

\(\displaystyle{ 5x^{2}-15x+22\equiv 0(mod \ 6)}\)

Czy jest na to jakiś algorytm rozwiązywania, czy poprostu trzeba zawsze badać wszystkie możliwości? Jak rozwiązujecie tego typu kongruencje?
Pytam, aby się upewnić, czy nie istnieje innego rodzaju metoda...

12. Jakie liczby między 2320 i 2350 są pierwsze?

Czy są jakieś pomysły na jeszcze to zadanie?

"Rozwiązać w liczbach całkowitych równanie"

No właśnie... tak teraz mi naszła taka wątpliwość... jaka jest różnica w zadaniach o poleceniu "Rozwiązać w liczbach całkowitych równanie" , a "Rozwiązać w liczbach naturalnych równanie"? Na coś trzeba szczegulnie uważać? Jakoś inaczej sie liczy?