<prompt> Ni nambari gani kamili n inatosheleza 0le n101 na 100nequiv 72pmod 101?  <response>: Ninagundua kuwa moduli 101 ni nambari kuu, kwa hivyo kunaweza kuwa na sifa nzuri za hesabu za kawaida ambazo ninaweza kutumia. Jambo moja ninalojua ni kwamba ikiwa a na b ni nambari kamili ambazo ni muhimu kwa 101, basi kuna x kamili kama vile axequiv bpmod 101. Haya ni matokeo ya algorithm ya Euclidean na ukweli kwamba 101 ni bora. Katika tatizo hili, ninataka kupata n vile 100nequiv 72pmod 101. Kwa kuwa 100 na 101 ni za hali ya juu, ninaweza kutumia mali niliyotaja hivi karibuni na kutafuta nambari kamili x kiasi kwamba 100xequiv 1pmod 101. Nikipata x kama hiyo, basi ninaweza kuzidisha pande zote mbili kwa 72 na kupata 10072xequiv 72pmod 101. Halafu naweza kuona kuwa n72x ni suluhisho la shida ya asili. Kwa hivyo nitapataje x? Kweli, njia moja ni kutumia algoriti iliyopanuliwa ya Euclidean, ambayo hupata nambari kamili x na y kiasi kwamba 100x101y1. Kisha ninaweza kupunguza pande zote mbili modulo 101 na kupata 100xequiv 1pmod 101. Ili kutumia algoriti iliyopanuliwa ya Euclidean, ninaanza kwa kuandika 101 kama kizidishio cha 100 pamoja na salio: 1011001. Kisha ninaandika 100 kama kizidishio cha 1 pamoja na salio: 1001cdot 1000. Ninagundua kuwa salio ni sifuri, kwa hivyo ninasimama hapa. Ninaweza kufanya kazi nyuma na kueleza 1 kama mchanganyiko wa mstari wa 100 na 101: 1101-100. Hii inamaanisha kuwa x-1 na y1 ni suluhisho la 100x101y1. Kwa hivyo, x-1 ni suluhisho la 100xequiv 1pmod 101. Ninaweza kuangalia hii kwa kuichomeka: 100-1equiv -100equiv 1pmod 101, kwa kuwa -100 na 1 hutofautiana kwa kuzidisha 101. Sasa nina x -1, ninaweza kuzidisha pande zote mbili kwa 72 na kupata 100-72equiv 72pmod 101. Hata hivyo, hili si suluhu pekee, kwa kuwa kuna nambari kamili nyingi ambazo zinalingana na -72 modulo 101. Tatizo linaomba nambari kamili n inayotosheleza 0le n101, kwa hivyo ninahitaji kupata suluhu dogo zaidi chanya. Ninaweza kufanya hivi kwa kuongeza 101 hadi -72 hadi nipate nambari chanya. Ninaona kwamba -7210129, ambayo ni chanya na chini ya 101. Kwa hiyo n29 ni suluhisho ndogo zaidi chanya kwa tatizo la awali. 