Veky's MathLand -- EM1&2

NZM ~ zadaci

Z Na~dite NZM(r,s) i prika~zite ga u obliku kr+ls , za k,l@Z :

r=226304 , s=483327
r=1976072 , s=4866752

Rj (a):

 483327 : 226304 =  2 i ost. 30719
 226304 :  30719 =  7 i ost. 11271
  30719 :  11271 =  2 i ost. 8177
  11271 :   8177 =  1 i ost. 3094
   8177 :   3094 =  2 i ost. 1989
   3094 :   1989 =  1 i ost. 1105
   1989 :   1105 =  1 i ost. 884
   1105 :    884 =  1 i ost. 221
    884 :    221 =  4 i ost. 0

  4    1    1    1    2    1    2    7    2 
0 1   -1    2   -3    8  -11   30 -221  472

NZM(483327,226304)=221=-221*483327+472*226304

(b):

 4866752 : 1976072 =  2 i ost. 914608
 1976072 :  914608 =  2 i ost. 146856
  914608 :  146856 =  6 i ost. 33472
  146856 :   33472 =  4 i ost. 12968
   33472 :   12968 =  2 i ost. 7536
   12968 :    7536 =  1 i ost. 5432
    7536 :    5432 =  1 i ost. 2104
    5432 :    2104 =  2 i ost. 1224
    2104 :    1224 =  1 i ost. 880
    1224 :     880 =  1 i ost. 344
     880 :     344 =  2 i ost. 192
     344 :     192 =  1 i ost. 152
     192 :     152 =  1 i ost. 40
     152 :      40 =  3 i ost. 32
      40 :      32 =  1 i ost. 8
      32 :       8 =  4 i ost. 0

  4  1  3  1  1   2   1   1   2    1    1    2    4      6     2       2 
0 1 -1  4 -5  9 -23  32 -55 142 -197  339 -875 3839 -23909 51657 -127223

NZM(4866752,1976072)=8=51657*4866752-127223*1976072

L Appleti~t koji bi mogao pomo~ti pri rje~savanju ovakvih (i kasnijih) zadataka: Writing the gcd(a, b) as an Integral Linear Combination of a and b (dno stranice). S gcd(a,b) (ili ~cak samo (a,b) ) tamo je ozna~cena najve~ta zajedni~cka mjera a i b .

P NZM(91,65)

 91 : 65 =  1 i ost. 26
 65 : 26 =  2 i ost. 13
 26 : 13 =  2 i ost. 0

  2    2    1 
0 1   -2    3

NZM(91,65)=13=-2*91+3*65

Z (pismeni, 2002-07-03) Izra~cunajte najve~tu zajedni~cku mjeru brojeva 2²⁰⁰⁴-1 i 2²⁰⁰²-1 .

Rj U prvom koraku Euklidovog algoritma dijelimo 2²⁰⁰⁴-1 s 2²⁰⁰²-1 . Lako se vidi da je kvocijent 4 , a ostatak je onda 3 : 2²⁰⁰⁴-1=4(2²⁰⁰²-1)+3 Sada treba odrediti ostatak pri dijeljenju 2²⁰⁰²-1 s 3 .

U tu svrhu primijetimo: 2²⁰⁰² daje isti ostatak pri dijeljenju s 3 kao i (-1)²⁰⁰²(=1) . ( 2 i -1 daju isti ostatak pri dijeljenju s 3 , pa i njihove 2002ge potencije tako~der daju isti ostatak pri dijeljenju s 3 . Detaljnije o tome u pri~ci o kongruencijama.) To je zato ~sto je 2²⁰⁰²=(3-1)²⁰⁰², a to se mo~ze raspisati po binomnom teoremu kao suma od 2003 ~clana. No prvih 2002 ~clanova imaju faktor 3 na neku prirodnu potenciju, tako da su svi djeljivi s 3 . Odnosno, ostatak pri dijeljenju cijele sume s 3 jednak je kao ostatak pri dijeljenju zadnjeg pribrojnika s 3 , a to je (2002povrh2002)*(-1)^2002=1 .

Sve u svemu, 2²⁰⁰² daje ostatak 1 pri dijeljenju s 3 , pa je 2²⁰⁰²-1 djeljivo s 3 . Odnosno, Euklidov algoritam zavr~sava nakon dva koraka, i tra~zena NZM je 3 .

D Za brojeve a i b ka~zemo da su relativno prosti ako je NZM(a,b)=1 .

SPrimijetimo, u terminima djeljivosti, to zna~ci da jedino broj 1 dijeli oba broja a i b . U terminima linearnih kombinacij~a, to zna~ci da se 1 mo~ze prikazati kao linearna kombinacija a i b s cjelobrojnim koeficijentima. Prvo, vrijedi i obrat toga: ako se 1 mo~ze tako prikazati, tada je sigurno najmanji prirodni broj koji se mo~ze tako prikazati (jer je najmanji prirodni broj uop~te:), pa je 1=NZM(a,b) , odnosno a i b su relativno prosti. To nam govori da kad god dobijemo negdje 1=ka+lb za cjelobrojne k i l , a i b moraju biti relativno prosti.
A drugo, ako je 1=ka+lb za k,l@Z , tada za bilo koji prirodni m , m=(km)a+(lm)z , odnosno relativno prosti brojevi (i samo oni) imaju va~zno svojstvo da se _svaki cijeli broj mo~ze napisati kao njihova linearna kombinacija s cjelobrojnim koeficijentima_. Metafori~cki, njihova "linearna ljuska" (nad Z) je cijeli Z.