Selamat datang di blog kami. Semoga bisa membantu teman-teman dalam mata pelajaran matematika pada contoh soal dan pembahasan "Algoritma Euclid dan Kongrensi Modulo".
ALGORITMA EUCLID
1.Tentukan FPB dari $53$ dan $7$!
A. $3$
B. $0$
C. $4$
D. $7$
E. $1$
Pembahasan:
$53 = 7.7+4$
$7 = 1.4+3$
$4 = 1.3+1$
$3 = 1.3+0$ (Karena sisanya sudah $0$,maka FPB-nya adalah sisa sebelumnya)
Jadi, FPB dari $53$ dan $7$ adalah $1$
jawaban: (E)
2.Tentukan FPB dari $1.398$ dan $2.058$!
A. $8$
B. $0$
C. $36$
D. $6$
E. $2$
Pembahasan:
$2.058 = 1.1.398+660$
$1.398 = 2.660+78$
$660 = 8.78+36$
$78 = 2.36+6$
$36 = 6.6+0$
Jadi, FPB dari $1398$ dan $2058$ adalah $6$
Jawaban: (D)
3.Carilah FPB dari $175$ dan $245$ !
A. $35$
B. $0$
C. $70$
D. $1$
E. $2$
Pembahasan:
$245 = 175.1+70$
$175 = 70.2+35$
$70 = 35.2$ —–> tidak bersisa
Jadi, FPB dari $175$ dan $245$ adalah $35$.
Jawaban: (A)
4.Tentukan FPB dari $437$ dan $621$ !
A. $23$
B. $5$
C. $460$
D. $1$
E. $0$
Pembahasan:
$621 = 437.1+184$
$437 = 184.2+69$
$184 = 69.2+46$
$69 = 46.1+23$
$46 = 23.2$ —–> tidak bersisa
Jadi, FPB dari $437$ dan $621$ adalah $23$.
Jawaban: (A)
5.Tentukan FPB dari $3.087$ dan $6.958$ !
A. $3$
B. $49$
C. $4$
D. $15$
E. $1$
Pembahasan:
$6.958 = 3087.2+784$
$3.087 = 784.3+735$
$784 = 735.1+49$
$735 = 49.15$ —–> tidak bersisa
Jadi, FPB dari $3.087$ dan $6.958$ adalah $49$.
Jawaban: (B)
6.Tentukan FPB($9.800$, $180$)
A. $3$
B. $49$
C. $4$
D. $80$
E. $20$
Pembahasan:
$9.800 = 180.54+80$
$180 = 80.2+20$
$80 = 20.4$
Jadi FPB dari $9.800$ dan $180$ adalah $20$
Jawaban: (E)
7.Tentukan FPB($10.587$, $534$)
A. $3$
B. $21$
C. $7$
D. $1$
E. $69$
Pembahasan:
$10.587 = 534.19+441$
$534 = 441.1+9$
$441 = 93.4+69$
$93 = 69.1+24$
$69 = 24.2+21$
$24 = 21.1+3$
$21 = 3.7$
Jadi FPB dari $10587$ dan $534$ adalah $3$
Jawaban: (A)
8.Tentukan FPB($321$, $843$)
A. $13$
B. $39$
C. $2$
D. $0$
E. $3$
Pembahasan:
$843 = 2.321+201$
$321 = 1.201+120$
$201 = 1.120+81$
$120 = 1.81+39$
$81 = 2.39+3$
$39 = 13.3+0$
Jadi, FPB dari $321$ dan $843$ adalah $3$
Jawaban: (E)
9. Tentukan FPB ($43.579$, $4.567$)
A. $12$
B. $11$
C. $1$
D. $9$
E. $2$
Pembahasan:
$4.567 = 1.3.579+988$
$3.579 = 3.988+615$
$988 = 1.615+373$
$615 = 1.373+242$
$373 = 1.242+131$
$242 = 1.131+111$
$131 = 1.111+20$
$111 = 5.20+11$
$20 = 1.11+9$
$11 = 1.9+2$
$9 = 4.2+1$
$2 = 2.1+0$
Jadi, FPB dari $3.579$ dan $4.567$ adalah $1$
Jawaban: (C)
10. Tentuka FPB ($897$, $1.157$ dan $1.677$)
A. $12$
B. $13$
C. $4$
D. $0$
E. $52$
Pembahasan:
$1.677 = 1.1.157+520$
$1.157 = 2.520+117$
$520 = 4.117+52$
$117 = 2.52+13$
$52 = 4.13+0$
Jadi FPB dari $897$,$1.157$ dan $1.677$ adalah $13$
Jawaban: (B)
KONGRENSI MODULO
11. Angka satuan dari $357^5.117^9$ adalah....
A. $1$
B. $3$
C. $5$
D. $7$
E. $9$
Pembahasan:
Angka satuan dapat dicari dengan menggunakan modulo $10$.
Sebelum itu, perhatikan bahwa angka satuan dari perpangkatan $7$ memiliki pola berulang: $7,9,3,1$. Dalam hal ini, $7^14$ memiliki satuan yang sama dengan $7^2$.
$357^5.117^9≡7^5.7^9$ (mod $10$)
≡$7^14$ (mod $10$)
≡$7^2$ (mod $10$)
≡$49$ (mod $10$)
=$9$ (mod $10$)
Jadi, angka satuan dari $357^5.117^9$ adalah $9$
(Jawaban E)
12. Angka satuan dari $7^{2020}$ mod $10$ adalah....
A. $1$
B. $3$
C. $5$
D. $7$
E. $9$
Pembahasan:
Angka satuan dicari menggunakan modulo $10$.
$7^{2020}$ (mod $10$)≡($7^2)^{1010}$ (mod $10$)
≡$49^{1010}$ (mod $10$)
≡($4×10+9)^{1010}$ (mod $10$)
≡$9^{1010}$ (mod $10$)
≡($−1)^{1010}$ (mod $10$)
≡$1$ (mod $10$)
Jadi, angka satuan dari $7^{2020}$ adalah $1$
(Jawaban A)
13. Jika $8^{79}$= x (mod $5$) dan $0 ≤ x ≤ 4$, maka nilai x = ....
A. $10$
B. $4$
C. $20$
D. $1$
E. $0$
Pembahasan:
$8^{79} = 3^{79}$ (mod $5$)
=($3^4)^{19}.3^2$ (mod $5$)
=($16.5+1)^{19}.9$ (mod $5$)
= $1^{19}.9$ (mod $5$)
= $9$ (mod $5$)
= $4$ (mod $5$)
Jadi nilai x = $4$
Jawaban: (B)
14. Berapa sisa $4.6$ dibagi $5$ ?
A. $15$
B. $10$
C. $4$
D. $1$
E. $5$
Pembahasan :
($4.6$) mod $5$ = ($5–1$)($5+1$) mod $5$
= ($5^2-1$) mod $5$
= –$24$ mod $5$
= (-$5.5+1$) mod $5$
= -$1$ mod $5$
= ($5–1$) mod $5$
= $4$ mod $5$
Jadi $4.6$ dibagi $5$ sisanya $4$
Jawaban: (C)
15. Berapa sisa $7^{77}$ dibagi $12$ ?
A. $7$
B. $9$
C. $6$
D. $10$
E. $12$
Pembahasan :
$7^{77}$ mod $12$ = $7.7^{76}$ mod $12$
= $7.(7^2)^{38}$ mod $12$
= $7.49^{38}$ mod $12$
= $7.(4.12+1)^{38}$ mod $12$
= $7.1^{38}$ mod $12$
= $7$ mod $12$
= $7$
Jadi $7^{77}$ dibagi $12$ sisanya $7$
Jawaban: (A)
16. Berapakah sisa $3^{2001}$ dibagi $100$?
A. $4$
B. $9$
C. $11$
D. $10$
E. $3$
Pembahasan :
$3^5 = 243$ (mod $100$)
= ($2.100 + 43$) (mod $100$)
= $43$ (mod $100$)
$3^{10} = (3^5)^2$
= $43.43$ (mod $100$)
= $1849$ (mod $100$)
= ($18.100 + 49$) (mod $100$)
= $49$ (mod $100$)
$3^{20} = (3^{10})^2$
= $49.49$ (mod $100$)
= $2401$ (mod $100$)
= $(24.100 + 1$) (mod $100$)
= $1$ (mod $100$)$
$3^{2001} = $3^{20})^{100}.3$
= $(1^{100})3$ (mod $100$)
= $3$ (mod $100$)
Jadi $3^{2001}$ dibagi $100$ sisanya $9$
Jawaban: (B)
17. Sisa pembagian $4^{18}.19^{80}$ oleh $9$ adalah....
A. $1$
B. $3$
C. $5$
D. $7$
E. $9$
Pembahasan:
$4^1=4$ (mod $9$)
$4^2=7$ (mod $9$)
$4^3=1$ (mod $9$)
Oleh karena itu, kita peroleh
$4^{18}=(4^3)^6$ (mod $9$)
= $1^6$ (mod $9$)
= $1$ (mod $9$)
Selanjutnya, akan dicari sisa pembagian $19^{80}$ oleh $9$. Perhatikan bahwa $19$ dibagi $9$ bersisa $1$.
$19 = 1$ (mod $9$)
→$19^{80} = 1^{80}$ (mod $9$)
$19^{80} = 1$ (mod $9$)
Dengan demikian
$4^{18}.19^{80} = 1.1$ (mod $9$)
= $1$ (mod $9$)
Jadi sisa pembagiannya adalah $1$
Jawaban: (A)
18. Berapakah sisa dari $(3^{2011})-1$ dibagi $61$ ?
A. $10$
B. $12$
C. $4$
D. $8$
E. $2$
Pembahasan :
$3^2 = 9$ (mod $61$)
$3^4 = (3^2)^2$
=$81$ (mod $61$)
=($1.61 + 20$) (mod $61$)
=$20$ (mod $61$)
$3^8= (3^4)^2$
=$20.20$ (mod $61$)
=$400$ (mod $61$)
=$(5.61 + 34$) (mod $61$)
=$34$ (mod $61$)
$3^{10} = 3^2.3^8$
=$9.34$ (mod $61$)
=$306$ (mod $61$)
=($5.61 + 1$) (mod $61$)
=$1$ (mod $61$)
$3^{2011} =3^{2000} + 10 + 1$
=$(3^{10})^{200}.3^{10}.3$
=$1^{200}.1^{10}.3$ (mod $61$)
=$1.1.3$ (mod $61$)
=$3$ (mod $61$)
Karena $3^{2011}$ dibagi $61$ sisanya $3$, sehingga $(3^{2011})-1 61$ sisanya $2$.
Jawaban: (E)
19. Berapakah sisa pembagian dari $(32+13)^2$ dibagi $8$?
A. $6$
B. $1$
C. $4$
D. $8$
E. $2$
Pembahasan :
$(32+13)^2 = 32^2 + 2.32.13 + 13^2$
= $32^2 + 2.32.13 + 169$
Karena $32$ habis dibagi $8$, berakibat $32^2$ habis dibagi $8$ dan $2.32.13$ juga habis dibagi $8$.
Jadi jika ada perkalian yang merupakan faktor $8$, jika dikali berapapun lalu di bagi $8$ pasti tidak ada sisanya.
Sehingga, kita tinggal memperhatikan $169$, yaitu berapa sisa dari $169$ dibagi $8$.
Jadi $169$ mod $8 = (21.8 + 1)$ mod $8 = 1$ mod $1$. Jadi, $(32+13)^2$ dibagi $8$ sisanya $1$.
Jawaban: (B)
20. Hasil dari ($1+2+3+65+66+67+79+80+99$) (mod $4$) adalah....
A. $14$
B. $3$
C. $5$
D. $7$
E. $9$
Pembahasan:
Masing-masing bilangan dicari sisa hasil baginya terhadap $4$, lalu dijumlahkan, seperti berikut.
($1+2+3+65+66+67+79+80+99$)(mod $4$)
≡($1+2+3+1+2+3+3+0+1+3$)(mod $4$)
≡$19$(mod $4$)≡$3$(mod $4$)
Jadi, sisa hasil baginya adalah $3$
Jawaban: (B)
Disusun oleh: Sugesti Rahayu (2110251023) dan Silvia Rasyida (2110251003)
SOAL DAN PEMBAHASAN ALGORITMA EUCLID DAN KONGRENSI MODULO
Selesai