Maradékos osztás nagy számokkal számológép nélkül?

Mondjuk ezt még papíron is simán kiszámolod pikk-pakk

de lehet ezt-azt egyszerűsíteni, meg átírni, meg prímszámok szorzataként felírni, és majd lehet valami csoda történik, meg algebrai mókolás, csak fölösleges

de simán kiszámolod a fentit papíron se perc alatt is

15^5= 15x15x15x15x15 = ... =759375

4176-ot szorzok 100-zal = 417600

kivonom egymásból és 341775-ben keresünk márcsak

abból kivonunk mittudomén kb 4176x 80-at könnyen számoljuk,334080 lesz

kivonjuk kettőt egymásból és marad 7695 ami már baráti

abból 4176-t és voálá, annyi lesz a maradék

(A magyar nem az anyanyelvem és ez nagyon nem egyszerű matekot írni egy idegen nyelven, tehát előre bocs a hibákért/lehet hogy nem egyértelmű, ebben az esetben kérlek szólj)

Úgy gondolkodd, hogy 15 = 10+5. 15^2 = 15*10 + 15*5 (azaz 15*10/2) = 225. 15^3 = 2250 + 1125 = 3375. 15^4 = 33750 + 16875 = 50625. 15^5 = 506250 + 253125 = 759375.

Aztán döntsd ki, hogy 759375 4176-tal osztva az kb mennyi, és minden hasonló számmal számolj. Pl egyszerűen látható, hogy 759375/4176 az kicsit kevesebb, mint 200. Szóval 200-zal szorozz a 4176-ot, normálisan 835200 az eredmény. Úgy láthatod, hogy 835200-759375 az kb 80000, azaz kb 20*4176.

Aztán kivond ezt 835200-ból: 20*4176=83520 <=> 835200-83520 = 751680 (ez 4176*200 - 4176*20 = 4176*180). Majd közeledünk az elvárt eredményhez. Adj hozzá 4176-ot: 751680 + 4176 = 755856 (4176*181). Megint: 755856 + 4176 = 760032 (4176*182). Ez most 759375 fölött van, tehát tudjuk hogy 759375 pont 4176*181 és 4176*182 között áll, azaz 15^5 = 4176*181 + maradék.

Most egy utolsó kivonás: 759375 - 4176*181 = 759375 - 755856 = 3519.

Szóval: 15^5 mod 4176 = 3519.

Mindezt kézzel, fejjel számoltam, és nem vagyok zseni, úgyhogy neked is teljesen lehetséges, remélem segíthettem valamiben :)

ha nem ilyen kis számok lennének, akkor lehetne gondolkozni rajta, hogy lehet-e értelmesebb megoldás, egyébként többfélén is lehetne

mondjuk bal és a jobb oldali is osztható 3-mal... például (mivel számjegyek összege osztható 3-mal...) és errefelé elindulni, kacifántosan

de lehet simán papíron is osztani a kettőt, aztán megnézni mi lesz a maradék, annyira nem nagy számok, na meg a fentiből már tudod, hogy mennyi lesz a vége, meg azt is, hogy mennyi a fenti elosztva a másikkal :D

ja, amúgy 3. ma 02:24-es és 1. ma 02:10-es vagyok

látom időközben más is írta hasonló logikával

759375 / 4176 =

7593'75 / 4176 = 1

3417

7593'7'5 / 4176 = 18

34177

..769

7593'7'5 / 4176 = 181

34177

..7695

...3519 - ennyi

én voltam az 1.-es, 3-as, 4-es, meg ez a hozzászóló

És még lehetne még más megoldási mód is, ha valóban nagy számok lennének :D

mondjuk nem férne ki a számológépen, meg programot is nehezen írnál rá simán valamit, mert nem férne el a változókban, meg olyan lenne a nyelv, hogy nehezen támogatná az ilyeneket

én voltam az 1.-es, 3-as, 4-es, meg 5-ös, meg ez a hozzászóló

Amikor hatvány maradékát szeretnénk megtudni, akkor érdemes azt fejben tartani, hogy elég csak a maradékot megszorozni az alappal;

15 maradéka 15.

15*15=225 maradéka 225.

225*15=3375 maradéka 3375.

3375*15=50625 maradéka 513.

Eddig mindig ugyanannyi volt a maradék, mint maga a szám, úgyhogy a változást csak most láthatjuk:

513*15=7695 maradéka 3519.

De mint írták is, a 15^5 még emberileg sem számít nagy számnak, de mondjuk egy 15^100 kiszámítása papíron eléggé hosszadalmas lenne, hát még a végigosztása. Az általam leírt módszer viszont ezeket a számításokat nagyságrendekkel le tudja rövidíteni.

Az ilyen jellegű feladatokhoz egyébként az Euler-Fermat-tételt szoktuk használni:

[link]

Bár ennél a konkrét példánál nehezen tudjuk alkalmazni, mivel a fi(4176) értéke sokkal nagyobb, mint 15, de ha mondjuk 15^2000 maradéka lenne a kérdés, akkor nagyban lerövidítené a számolás menetét a tétel alkalmazása.