Mennyi a 2^37 -en szám 21-gyel való osztási maradéka? ^ hatványt jelöl

2^6=64

3*21 + 1= 64

2^36=64^6=(3*21+1)^6 = 3^6 * 21^6 + ...+ 3*21 + 1

2^37=2^36 *2 = ...3*21*2 + 2

2^37/21 m=2

VAGY kicsit pontosabban, nem "megsejtem hogy"-al:

2/3 -> 2

4/3 -> 1

...

=> 2,1,2,1,2,1,...

37. eleme: 2

2/7 -> 2

4/7 -> 4

8/7 -> 1

16/7 ->2

...

=> 2,4,1,2,4,1,2,4,1,...

37. eleme: 2

Tehát 2^37-2 7-tel és 3-mal is osztható. Tehát 21-el is. Így 2^37 = k*21 +2

VAGY a két szám osztási maradékainak periódusa:

3: 2

7: 3

Legkisebb közös többszörösök: 2*3=6, tehát 2^6 és többszörösei oszthatóak 21-el...

Hülyeséget írtam utolsó mondatként , helyette: 6 ugrásonkét ismétlődik a 21-el való osztás utáni maradék. 2^(37-6*k)-nak is ugyan az a maradéka. Tehát 2^(37-6*6)=2^1=2

2/21 -> 2

Így

2^37/21 -> 2

Egyszerűbb feladatoknál tudunk így ügyeskedni, kicsit bonyolultabbaknál az Euler-Fermat-tételre van szükségünk:

[link]

Tehát:

2^37 = ? mod(21)

A 2 és a 21 egymáshoz relatív prímek, tehát használható a linkelt tétel. Eszerint phi(37)-re van szükségünk, vagyis azon számok számára, amik a 37-nél kisebbek, pozitív egészek és relatív prímek a 37-hez (vagyis legnagyobb közös osztójuk vele 1). Mivel a 37 prímszám, ezért phi(37)=36, vagyis a tétel alapján:

2^36 = 1 mod(21), ezt egy egyszerű 2-vel való szorzás után:

2^37 = 2 mod(21), tehát a 2^37 21-es maradéka valóban 2.

2^5=32=21*1+11

Mineen kétszerezésnél a maradékokat hatványozzuk.

11, 1, 2, 4, 8, 16, 11

Minden 5. ismétlődik. Innen már egyszerű