najveca zajednicka mjera

[pinkgirl]

M(2^20+1,2^15-1)=?


rjesavajuci zadatak dodemo do tog da je osstatak veci od djelitelja...
jel to tako uvijek bude, pa da moramo nastimavat brojeve ili?

btw, otvorih novi topic da ne bu zabune...

[vinko]

Ostatak ne moze biti veci od djelitelja. Zacjelo ste negdje pogrijesili.

M(2^20+1, 2^15-1) = M(2^15-1, 33) = M(33, 31) = M(31, 2) = M(2, 1) = 1

[Spectre]

Ja također ne kužim izračunavanje NZM Na kalkulatoru mogu izračunati, kada dobijem broj veći od broja s kojim dijelim, samo nastavim dijeliti sve dok ne padne ispod njega, no nemam blage kako se ovakvi zadaci rješavaju samostalno.

_________________
Cry havoc, and let loose the dogs of war!

[crnka]

Ja takoder imam taj problem, pa ako ovdje ima netko pametan, mislim da bi mu svi bili zahvalni da nam objasni to prije kolokvija u 15 h!!!

[crnka]

Mislim da sam skuzila...

M(2^20+1,2^15-1)=....

2^20+1=2^5(2^15-1)+2^5+1

M(2^20+1,2^15-1)=M(2^15-1,2^5+1)=...

2^15-1=2^10(2^5+1)-2^10-1

M(2^15-1,2^5+1)=M(2^10+1,2^5+1)=...

2^10+1=2^5(2^5+1)-2^5+1

M(2^10+1,2^5+1)=M(2^5+1,2^5-1)=M(33,31)=1

Evo, mislim da je ovo tocno, pa vi provjerite i ispravite me ak ne valja...

[vinko]

Moze i ovako kako je crnka napisala, a mozemo i pojednostaviti:

Dakle cijelo vrijeme koristimo pravilo
M(a, 0)=a i M(a, b) = M(b, a mod b)

Dakle, M(2^20+1, 2^15-1) = M(2^15-1, (2^20+1) mod (2^15-1)) = M(2^15-1,33)
M(2^15-1,33)=M(33,(2^15-1) mod 33), = M(33, 31)
M(33,31) = M(31, 33 mod 31) = M(31, 2)
M(31,2) = M(2, 31 mod 2) = M(2,1)
M(2,1) = M(1, 2 mod 1) = M(1,0) = 1

[Spectre]

Svaka čast Vinko, mislim da bi svatko sad to trebao shvatiti! Puno Vam hvala!

_________________
Cry havoc, and let loose the dogs of war!