Hogyan lehet segédeszköz nélkül (számológép/számítógép) két nagy szám hányadosát rövid idő alatt relatív prímekké egyszerűsíteni, vagy megállapítani, hogy már azok (azaz, hogy már nem lehet tovább egyszerűsíteni)?

Euklideszi algoritmussal:

Maradékosan osztod a nagyobbik számot a kisebbel, aztán a maradékra és a kisebb számra eljátszod ugyanezt addig, amíg egyszer 0 nem lesz a maradék. A 0 előtti utolsó maradék a két szám legnagyobb közös osztója, ezzel kell egyszerűsíteni a törtet.

6 darab 9-est szerettél volna írni? A GyK le szokott vágni, az ennél többet. De mindegy, példának megteszi:

223 878 902/999 999.

223 878 902-ben a 999 999 megvan 223-szor, marad

223 878 902 – 223*999 999 = 878 902 + 223 = 879 125.

Most 999 999 lesz a nagyobbik szám, és 879 125 a kisebbik.

999 999-ben a 879 125 megvan 1-szer, marad a

999 999 – 879 125 = 120 874.

879 125-ben a 120 874 megvan 7-szer, marad 33 007.

120 874-ben a 33 007 megvan 3-szor, marad 21 853.

33 007 = 1*21 853 + 11 154,

21 853 = 1*11 154 + 10 699,

11 154 = 1*10 699 + 455,

10 699 = 23*455 + 234,

455 = 1*234 + 221,

234 = 1*221 + 13,

221 = 17*13 + 0.

Itt először 0 a maradék, ez előtt 13 volt, tehát 13 a két eredeti szám legnagyobb közös osztója, ezzel lehet egyszerűsíteni.

223 878 902/13 = 17 221 454,

999 999/13 = 76 923,

223 878 902/999 999 = 17 221 454/76 923.

Úgy néz ki, hogy ez esetben a prímtényezőkre bontás gyorsabb lett volna… De így is megvolt a legnagyobb közös osztó 11 osztással. Ilyen 10^10 nagyságrendű számoknál átlagosan 20 osztásra van szükség, legfeljebb pedig 50-re, viszont általános esetben ez a legjobb módszer. Nem tudom, hogy mennyire preparáltak a többi példáid.