Răspuns
Explicație pas cu pas:
Putem reforma 2 ^ 2019/2019 ca 2 ^ 2019 / (3 * 673) unde 3 și 673 sunt numere prime și nu împart 2.
Astfel, aceste două pot satisface mica teoremă a lui Fermat, care spune că a este prim și nu împarte b atunci, b ^ (a-1) este congruent cu 1 (mod a).
Vom folosi această teoremă împreună cu algoritmul euclidian pentru a o rezolva.
Folosind mica teoremă a lui Fermat, putem scrie
2 ^ (673-1) este congruent cu 1 (mod 673)
= 2 ^ 672 este congruent cu 1 (mod 673)
= 2 ^ (672 * 3 + 3) este congruent cu 2 ^ 3 (mod 673)
= 2 ^ 2019 este congruent cu 8 (mod 673)
Prin urmare, restul când 2 ^ 2019 este împărțit la 673 este 8.
În mod similar, vom face cu 3:
2 ^ (3-1) este congruent cu 1 (mod 3)
= 2 ^ 2 este congruent cu 1 (mod 3)
= 2 ^ (2 * 1009 + 1) este congruent cu 2 (mod 3)
= 2 ^ 2019 este congruent cu 2 (mod 3)
Prin urmare, restul în acest caz este 2.
Acum folosind algoritmul euclidian putem scrie
673m + 8 = 3n + 2 = 2 ^ 2019
=> 673m = 3n-6
=> m = 3 (n-2) / 673
Fie (n-2) / 673 k.
Folosind m = 3k,
Putem rescrie, 673m + 8 ca
673 (3k) + 8 = 2 ^ 2019
2019k + 8 = 2 ^ 2019
Prin urmare, când 2 ^ 2019 este împărțit la 2019, restul este 8. !!s cu pas:
