szukanie zaawansowane
 [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Kobieta Offline
PostNapisane: 30 gru 2006, o 14:40 
Użytkownik

Posty: 50
Lokalizacja: malopolska
Mam takie zadanka i mam z nimi problem .... Prosze pomozcie(bede bardzo wdzieczna jezeli beda one dokladnie rozpisane) z gory dzieki !

1.Oblicz reszte z dzielenia liczby a=2^{1997}*3^{427}\quad przez\quad 25

2.Dla liczb a=1137 i b=348 wyznaczyc liczby calkowite x,y takie ze ax + by=NWD(a,b).

3.Sprawdzic czy liczby a=202 i 75 sa wzglednie pierwsze.

4.Dowiesc ze jezeli a i b sa wzglednie pierwsze to a� i b�sa wzglednie pierwsze.

5. Dowiesc, ze liczba n jest podzielna przez 8 wtedy i tylko wtedy gdy liczba utworzona z jej ostatnich trzech cyfr zapisu w systemie dziesietnym jest podzielna przez 8.

6.Dowiesc ze jezeli n jest dowolna liczba naturalna to liczba 10^{6n} - 1 jest podzielna przez 7.

7.Dowiesc ze jezeli n jest dowolna liczba naturalna to liczba 6^n + 6^{n+1} + 6^{n+2} + 2 jest podzielna przez 5.
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 14:50 
Gość Specjalny
Avatar użytkownika

Posty: 7136
Lokalizacja: Ruda Śląska
7.
6\equiv 1\pmod 5\\\forall_{k \in\mathbb{N}}\:6^k\equiv 1^k\equiv 1\pmod 5\Rightarrow 6^n\equiv 6^{n+1}\equiv 6^{n+2}\equiv 1\pmod 5\\6^n+6^{n+1}+6^{n+2}+2\equiv 1+1+1+2\equiv 5\equiv 0\pmod 5
6.
10\equiv 3\pmod 7\\10^6\equiv 3^6\equiv 729\equiv 1\pmod 7\\10^{6n}\equiv 1^n\equiv 1\pmod 7\\10^{6n}-1\equiv 0\pmod 7

3. W rozkładzie na czynniki pierwsze liczby 75 występują tylko potęgi 3 i 5, w rozkładzie 202 brak takich liczb \Rightarrow NWD(202;75)=1
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 14:56 
Administrator
Avatar użytkownika

Posty: 12708
Lokalizacja: Kraków
2.
Nie powinno być czasem NWW??

3.
202=2 \cdot 101\\
75=5^2\cdot 3
Brak wspólnych dzielników więc dane liczby są względnie pierwsze.
5. Zauważmy że 8|1000 Każda wielokrotnośc 1000 jest więc podzielna przez 8. By sprawdzić podzielność całej liczby należy zatem sprawdzić czy liczba utworzona z 3 jej ostatnich cyfr jest podzielna przez 8

6. Indukcjyjnie:
1. n=1\\
10^6-1=999 999=142857 \cdot 7\\
2.n=k\\
Z:10^{6k}-1=7a \quad \Longrightarrow 10^{6k}=7a+1\\
T:10^{6k+6}-1=7b\\
D"10^{6k+6}-1=10^6\cdot10^{6k}-1=10^6(7a+1)-1=10^6\cdot 7a +1 000 000 -1=7a\cdot10^6 +999 999=7(10^6a+142857)=7b \quad $gdzie$\ b=10^6a+142857\\
c.n.d
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 15:05 
Gość Specjalny
Avatar użytkownika

Posty: 3306
Lokalizacja: Lebendigentanz
1)
Mamy:
2^{7} = 128 \equiv 3 \pmod{25}\\
2^{10} = 1024 \equiv -1 \pmod{25}
Stąd:
2^{1990} = (2^{10})^{199} \equiv -1 \pmod{25}\\
2^{1997} = 2^{1990} \cdot 2^{7} \equiv -3 \pmod{25}

Mamy też:
3^{3} \equiv 2 \pmod{25}\\
3^{426} \equiv 2^{142} \pmod{25}\\
2^{142} = (2^{10})^{14} \cdot 2^{2} \equiv 4 \pmod{25}\\
3^{427} \equiv 12 \pmod{25}
Stąd:
2^{1997} \cdot 3^{427} \equiv -36 \pmod{25} \\
2^{1997} \cdot 3^{427} \equiv 14 \pmod{25}
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 15:17 
Gość Specjalny
Avatar użytkownika

Posty: 7136
Lokalizacja: Ruda Śląska
4. Niech
a=2^{a_2}\cdot 3^{a_3}\cdots p^{a_p}\\b=2^{b_2}\cdot 3^{b_3}\cdots p^{b_p}
(rozkład na czynniki pierwsze), wtedy
NWD(a,b)=2^{\min(a_2;b_2)}\cdots p^{\min(a_p;b_p)}=1\Rightarrow \forall_i\:\min(a_i;b_i)=0\Rightarrow \\\Rightarrow a_i=0\vee b_i=0 \Rightarrow 2a_i=0\vee 2b_i=0\Rightarrow\min(2a_i;2b_i)=0
więc
NWD(a^2;b^2)=2^{\min(2a_2;2b_2)}\cdots p^{\min(2a_p;2b_p)}=1
ckd.
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 15:23 
Administrator
Avatar użytkownika

Posty: 12708
Lokalizacja: Kraków
4.
$Przedstawmy liczby a i b jako iloczyny liczb pierwszych$\\
a=p_1\cdot p_2 \cdot ... \cdot p_n\\
b=q_1\cdot q_2 \cdot ... \cdot q_m\\
$Oczywiscie$\ p_1\neq p_2\neq...\neq p_n\neq q_1\neq q_2\neq ...\neq q_m $jako ze $\ a $ i$\ b $ sa wzglednie pierwsze$\\
$Po podniesieniu do kwadratu mamy:$\\
a^2=p_1^2\cdot p_2^2 \cdot ... \cdot p_n^2\\
b^2=q_1^2\cdot q_2^2 \cdot ... \cdot q_m^2\\
$Zauwazmy ze dla dowolnych dwoch liczb pierwszych x i y mamy: $x^2\neq y^2$ co mozemy bezposrednio przeniesc na czynniki pierwsze liczb\ $ a^2\  i\  b^2\ $ co w efekcie daje nam:$\\
\forall_{1\leq i \leq n, 1\leq j \leq m}\  p_i^2\neq q_j^2 $ co konczy dowod jako ze liczby $ a^2\ i \ b^2 $ nie maja wspolnego podzielnika$
Góra
Kobieta Offline
PostNapisane: 30 gru 2006, o 15:33 
Użytkownik

Posty: 50
Lokalizacja: malopolska
w 2 ma byc NWD

[ Dodano: 30 Grudzień 2006, 15:38 ]
mam jeszcze takie pytanie dlaczego jak mamy np. 1024\equiv-1(mod25) to dlaczego to modulo jest ujemne ? dlaczego nie jest 24 ?
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 15:41 
Użytkownik
Avatar użytkownika

Posty: 955
Lokalizacja: BFGD
Może też być ponieważ:
24{\equiv}-1{\pmod{5}}
Dlaczego? Ponieważ:
24+1{\equiv}25{\equiv}0{\pmod{25}}
Dla -1 jest łatwiej udowadniać po prostu (rachunkowo jest łatwiej)
Góra
Kobieta Offline
PostNapisane: 30 gru 2006, o 15:43 
Użytkownik

Posty: 50
Lokalizacja: malopolska
do 1. 2^{1997} \cdot 3^{427} \equiv -36 \pmod{25} \\ 2^{1997} \cdot 3^{427} \equiv 14 \pmod{25} i czemu nagle z -36 zrobilo sie 14 ? moze sie te wydadza glupie ale ja tego nie kapuje za bardzo :/
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 15:44 
Użytkownik
Avatar użytkownika

Posty: 955
Lokalizacja: BFGD
To samo:
Można tak zrobić bo:
-36{\equiv}14{\pmod{25}}
Góra
Kobieta Offline
PostNapisane: 30 gru 2006, o 15:48 
Użytkownik

Posty: 50
Lokalizacja: malopolska
eh ... ale to dziwne !
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 16:12 
Gość Specjalny
Avatar użytkownika

Posty: 3306
Lokalizacja: Lebendigentanz
Niekoniecznie - z twierdzenia o dzieleniu mamy:
-36 = -2\cdot 25 + 14, zatem reszta z dzielenia -36 przez 25 wynosi 14.
Czyli:
-36 \equiv 14 \pmod{25}
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 16:40 
Administrator
Avatar użytkownika

Posty: 12708
Lokalizacja: Kraków
Co do 1.:
NWD(1137,348)=3\\
1137x+348y=3\\
379x+116y=1\\
...
I tu się zacinam. Nie potrafię znaleźć x i y... Metoda prób i błędów odpada :P. Nie wiem jak to
zrobić by się nie narobić :roll: :arrow: :?: Wiem tylko że x musi być nieparzyste i dalej nic...
Góra
Mężczyzna Offline
PostNapisane: 30 gru 2006, o 20:16 
Gość Specjalny
Avatar użytkownika

Posty: 3306
Lokalizacja: Lebendigentanz
5. Załóżmy, że k, r to dowolne ustalone liczby całkowite, przy czym |r| < 1000 oraz:
r \equiv q \pmod{8}, gdzie q \in \{0, 1, 2, 3, 4, 5, 6, 7\}

Mamy:
1000 \equiv 0 \pmod{8}
Stąd:
k \cdot 1000 + r \equiv q \pmod{8}
Zatem reszta z dzielenia danej liczby przez 8 jest równa reszcie z dzielenia przez 8 liczby utworzonej z 3 ostatnich cyfr jej zapisu dziesiętnego. Stąd wynika w szczególności, że liczba jest podzielna przez 8 wtedy i tylko wtedy gdy jest podzielna przez 8 liczba utworzona z 3 ostatnich cyfr jej zapisu dziesiętnego. c.n.w.


2. Skorzystamy z rozszerzonego algorytmu Euklidesa:

1137 - \lfloor \frac{1137}{348}\rfloor \cdot 348 = 1137 - 3 \cdot 348 = 93 \\ \\
348 - \lfloor \frac{348}{93} \rfloor \cdot 93 = 348 - 3 \cdot 93 = 348 - 3 \cdot (1137 - 3 \cdot 348) = -3 \cdot 1137 + 10 \cdot 348 = 69\\ \\
93 - \lfloor \frac{93}{69} \rfloor \cdot 69 = 93 - 69 = 1137 - 3 \cdot 348 - (-3 \cdot 1137 + 10 \cdot 348) = 4\cdot 1137 - 13 \cdot 348 = 24\\ \\
69 - \lfloor \frac{69}{24} \rfloor \cdot 24 = 69 - 2 \cdot 24 =  -3 \cdot 1137 + 10 \cdot 348 - 2 \cdot (4\cdot 1137 - 13 \cdot 348) = -11 \cdot 1137 + 36 \cdot 348 = 21\\ \\
24 - \lfloor \frac{24}{21} \rfloor \cdot 21 = 24 - 21 = 4\cdot 1137 - 13 \cdot 348 = 4\cdot 1137 - 13 \cdot 348 - (-11 \cdot 1137 + 36 \cdot 348) = 15 \cdot 1137 - 49 \cdot 348 = 3\\ \\
21 - \lfloor \frac{21}{3} \rfloor \cdot 3 = 21 - 21 = 0

Stąd
\gcd (1137, 348) = 3 = 15 \cdot 1137 - 49 \cdot 348,
zatem
x = 15, \ y = -49

Zobacz też opis rozszerzonego algorytmu Euklidesa

Pozdrawiam
Góra
Kobieta Offline
PostNapisane: 31 gru 2006, o 12:43 
Użytkownik

Posty: 50
Lokalizacja: malopolska
Wielkie dzieki za odp ... ale jeszcze mam jedno pytanie jezeli chodzi o zad. 2 jezeli zamiast a=1137 i b=348 byly liczby np. a=135 i b=485 to chyba nie moglabym skorzystac z algorytmu Euklidesa ... bo wtedy nie ma liczby calkowistej z dzielenia a/b. I co w takim przypadku powinnam zrobic?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 16 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 (3 zadania) Wykaż, że liczby są podzielne przez ...  Anonymous  5
 (4 zadania) Sprawdz podzielność wyrażenia  Anonymous  3
 (4 zadania) Sprawdz podzielność liczb przez 10  Anonymous  4
 (3 zadania) Udowodnić podzielność przez 9. Wykazać, że  basia  2
 Dowód na poprawność zasady podzielności przez 9  magik100  12
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl