<prompt> Kokotoa 10-1pmod1001. Eleza jibu lako kama mabaki kutoka 0 hadi 1000, zikijumuishwa.  <response>: Ninajua kuwa 10-1 ina maana kinyume cha kuzidisha cha 10 modulo 1001. Yaani, ninahitaji kupata nambari kamili x kiasi kwamba 10xequiv 1pmod1001. Njia moja ya kufanya hivyo ni kutumia algoriti iliyopanuliwa ya Euclidean, ambayo hupata nambari kamili x na y zinazokidhi 10x1001y1. Ikiwa naweza kupata x na y kama hizo, basi x itakuwa kinyume ninachotafuta, na y haitakuwa na maana. Ili kutumia algoriti iliyopanuliwa ya Euclidean, ninaanza kwa kuandika hesabu 100110cdot 1001. Hii inamaanisha kuwa 11001-10cdot 100. Kwa hivyo nimepata x-100 na y1. Hata hivyo, -100 si modulo halali ya mabaki 1001. Ili kuifanya iwe halali, ninahitaji kuongeza au kuondoa vizidishio vya 1001 hadi nipate nambari kati ya 0 na 1000. Ninaona hiyo -1001001901, ambayo ni mabaki halali. Kwa hivyo, 10-1equiv 901pmod1001. 