נושא: תורת מספרים

נשלח בתאריך: 16 February 2006 בשעה 01:07 | IP רשוּם

שלום,

1.א. חשב את הספרה הראשונה (מימין) במספר 13 בחזקת 103.

  ב. חשב את שארית חלוקת המספר 257 בחזקת 57 במספר 50.

2. יהי a מספר אי זוגי ו n מספר טבעי. הוכח : שהמחלק המשותף הגדול של a בחזקת n פלוס 1 ו- a מינוס 1 שווה ל- 2 .

נשלח בתאריך: 16 February 2006 בשעה 12:46 | IP רשוּם

שני דברים את אמורה לדעת בנוגע לחישוב שארית:

1. a^b mod n = (a mod c) ^ b  mod n

2. zzz(a-1)^n mod a = (-1)^n

השני נובע מהראשון, והראשון הוא הכללה של כפל מודולו n

פתרון ל1 סעיף א

z 13^103 mod 10= (13^100 * 13 ^3) mod 10 =z

zzz (13^100 * 13 ^3) mod 10 = ((13)^2)^50)*((13 mod 3)^3) mod 10z

z(169)^50*3^3mod10=9^50 * 27 mod 10 = 7*(-1)^50 mod 10=7

פתרון ל1 סעיף ב

zzz 257^57 mod50 = 7^57 mod 50 = 7*7^56 mod 50 = 7*49^28 mod 50z

zzz7*(-1)^28 mod 50 = 7

לידיעתך, אני מנהל את פורום עזרה בש"ב בוואלה.