Re: Egzamin - 5 zadań

[chclony]

1. Jeśli to możliwe, rozwiąż równanie diofantyczne: 4x + 45y = 1
3. Wyznacz trzy ostatnie cyfry liczby \(7^{14404}\)
4. Ile jest liczb w przedziale [1, 1000] podzielnych przez 11, 13 lub 17?
5. Rzucamy trzema różnokolorowymi sześciennymi kostkami. Ile jest takich wyników, że ich iloczyn jest podzielny przez 3?
6. Oblicz S(7, 3)

[ebasse]

Ad.2

\(x\equiv 5 \pmod{6} \\
x\equiv 7 \pmod{11} \\
x=5+6k\\
5+6k \equiv 7 \pmod{11}\\
6k\equiv 2 \pmod{11}\\
3k\equiv 1 \pmod{11}\\

4 \cdot 11+1 = 45
3k\equiv 45 \pmod{11}\\
k\equiv 15 \pmod{11}\\
k=11u+15

x=5+6(11u+15)=5+66u+90=66u+95\\
x\equiv 95 \pmod{66}\\\)

Myślę że dobrze

[chclony]

Ad.2

\(x\equiv 5 \pmod{6} \\
x\equiv 7 \pmod{11} \\
x=5+6k\\
5+6k \equiv 7 \pmod{11}\\
6k\equiv 2 \pmod{11}\\
3k\equiv 1 \pmod{11}\\

4 \cdot 11+1 = 45
3k\equiv 45 \pmod{11}\\
k\equiv 15 \pmod{11}\\
k=11u+15

x=5+6(11u+15)=5+66u+90=66u+95\\
x\equiv 95 \pmod{66}\\\)

Myślę że dobrze

Ehh.. a czy coś takiego jest źle?


Mnie kupmela uczyła by zrobić taką tabelkę, a wynikiem jest te
\(\begin{cases}29=5(mod 6)\\ 29=7(mod 11)\end{cases}\)

[octahedron]

To jest ten sam wynik:

\(x\equiv 95\equiv 29\pmod{66}\)

Twój sposób też jest dobry, tylko trzeba pamiętać, że rozwiązaniem jest nie tylko \(29\), ale każda liczba postaci \(29+6\cdot 11\cdot k=29+66k,\ k\in C\).

[ebasse]

Nie znam tej metody, osobiście wczoraj uczyła mnie tego "irena" i zrobiłem tak jak umiem. Wynik sprawdziłem i zgadza sie. Ja na studiach brałem jeszcze inną metodę - tabelka z a, a', s, t, s', t', q. Tylko czasem mi sie nie zgadza lub ja źle coś licze.

[octahedron]

Zad. 3
\(x\) - liczba utworzona przez trzy ostatnie cyfry
\(x\equiv 7^{14404}\pmod{1000}
7^{14404}\equiv \(7^4\)^{3601}\equiv 2401^{3601}\equiv 401^{3601}\equiv (400+1)^{3601}\equiv \sum_{k=0}^{3601}{3601\choose k}400^k\cdot 1^{3601-k}\equiv
\equiv {3601\choose 1}400+{3601\choose 0}\equiv 3601\cdot 400+1\equiv 3600\cdot 400+400+1\equiv 401\pmod{1000}\)

Ostatnie cyfry to \(401\)

[chclony]

Zad. 3
\(x\) - liczba utworzona przez trzy ostatnie cyfry
\(x\equiv 7^{14404}\pmod{1000}
7^{14404}\equiv \(7^4\)^{3601}\equiv 2401^{3601}\equiv 401^{3601}\equiv (400+1)^{3601}\equiv \sum_{k=0}^{3601}{3601\choose k}400^k\cdot 1^{3601-k}\equiv
\equiv {3601\choose 1}400+{3601\choose 0}\equiv 3601\cdot 400+1\equiv 3600\cdot 400+400+1\equiv 401\pmod{1000}\)

Ostatnie cyfry to \(401\)

O mój..
Zgubiłeś/aś mnie już \(\equiv 401^{3601}\)
tutaj. Dalej było tylko gorzej

Skąd się wzięło 401? Czy już na tym etapie nie mogliśmy wiedzieć, że to są 3 ostatnie cyfry?

[octahedron]

\(2401\equiv 2\cdot 1000+401\equiv 401\pmod{1000}\)
bo
\(2\cdot 1000\equiv 0\pmod{1000}\)
i dlatego
\(2401^{3601}\equiv 401^{3601}\pmod{1000}\)
i może w tym miejscu już się da wywnioskować, że wyjdzie \(401\), ale ja nie umiem , więc dalej mamy dwumian Newtona i dostajemy w rozwinięciu wyrazy postaci:
\({3601\choose k}400^k={3601\choose k}4^k\cdot 100^k\)
dla \(k\ge 2\) potęga \(100^k\) dzieli się przez \(1000\), czyli \({3601\choose k}400^k\equiv 0\pmod{1000}\) i zostają tylko wyrazy dla \(k=0\) i \(k=1\), no a potem \(3600\cdot 400\equiv 36\cdot 40\cdot 1000\equiv 0\pmod{1000}\)

Możliwe, że da się prościej, sam się uczyłem rozwiązywania takich zadań, więc mogą być jakieś metody lepsze od mojej

[octahedron]

Zad. 1

\(NWD(4,45)=1=NWD(4,45,1)\)

Czyli równanie ma rozwiązanie.Stosujemy rozszerzony algorytm Euklidesa:

\(\begin{array}{|c|c|c|c|}\hline y&x&r&d\\\hline 1&0&45&-\\\hline 0&1&4&11\\\hline 1&-11&1&\\\hline\end{array}
\\
-11\cdot 4+1\cdot 45=1

x=-11+k\cdot\frac{45}{NWD(45,4)}=-11+45k
y=1-k\cdot\frac{4}{NWD(45,4)}=1-4k\)

[chclony]

Zad. 1

\(NWD(4,45)=1=NWD(4,45,1)\)

Czyli równanie ma rozwiązanie.Stosujemy rozszerzony algorytm Euklidesa:

\(\begin{array}{|c|c|c|c|}\hline y&x&r&d\\\hline 1&0&45&-\\\hline 0&1&4&11\\\hline 1&-11&1&\\\hline\end{array}
\\
-11\cdot 4+1\cdot 45=1

x=-11+k\cdot\frac{45}{NWD(45,4)}=-11+45k
y=1-k\cdot\frac{4}{NWD(45,4)}=1-4k\)

Heh.. te zadania mnie przerastają ;/
Dlaczego 11? Podzieliłeś/aś 45 tak by modulo wyszło 1?
Mógłbyś/mogłabyś mi rozwiązać podobny przykład?

Kod: Zaznacz cały

3x + 49y = 1

Ok, powiedzmy, że mam 1, 2, 3 i 7 rozwiązane. Dałbyś/dałabyś jeszcze radę 4, 5 i 6?

[radagast]

4.
Taki diagram:

ScreenHunter_329.jpg (16.2 KiB) Przejrzano 1469 razy

No i teraz: \(79+66+49+5+4+6=209\)
Jeśli czegoś nie rozumiesz - pytaj. Będę odpowiadać .

[chclony]

4.
Taki diagram:

ScreenHunter_329.jpg

No i teraz: \(79+66+49+5+4+6=209\)
Jeśli masz nie rozumiesz - pytaj. Będę odpowiadać .

Mógłbyś wyjaśnić skąd wziąłeś te dane?
Tj. 79, 66, 49, 5, 4, 6

[irena]

5.
Wszystkich możliwych wyników w trzech rzutach kostką jest \(6^3\).
Iloczyn trzech liczb jest podzielny przez 3, jeśli choć jedna liczba dzieli się przez 3.
Jeśli rozpatrzymy zdarzenie przeciwne - w żadnym z rzutów nie będzie liczby podzielnej przez 3 (czyli w żadnym rzucie nie otrzymamy 3 lub 6 oczek), to takich możliwości jest \(4^3\).
Wszystkich takich możliwości, w których choć jeden z wyników będzie wynosił 3 lub 6 oczek jest więc \(6^3-4^3=152\)

[radagast]

Mógłbyś wyjaśnić skąd wziąłeś te dane?
Tj. 79, 66, 49, 5, 4, 6

Zacznijmy od 0: liczb, które dzielą sie przez 11,13 i 17 jest 0 (bo \(11 \cdot 13 \cdot 17=2431\ \ 1000:2431=0\ r\ 1000\))
z kolei przez 13 i 17 dzielą się liczby podzielne przez 221 . 1000:221=4 r 116 (stąd 4)
z kolei przez 11 i 17 dzielą się liczby podzielne przez 187 . 1000:187=5 r 65 (stąd 5)
z kolei przez 11 i 13 dzielą się liczby podzielne przez 143 . 1000:143=6 r 142 (stąd 6)

teraz podzielnych prze 11 jest 90 (bo 1000:11=90 r 10 ) ale 5 i 6 juz jest policzone , zostało 79
podzielnych prze 13 jest 76 (bo 1000:13=76 r 12 ) ale 4 i 6 juz jest policzone , zostało 66
podzielnych prze 17 jest 58 (bo 1000:17=58 r 14 ) ale 4 i 5 juz jest policzone , zostało 49

No i teraz to dodać (bo "urozłączniłam" te zbiory) i juz

[radagast]

A mógłbyś powiedzieć co to znaczy S(7,3) ( nie znam tego oznaczenia)