A kínai maradéktétel

Egy régi gondolatolvasó trükkben a mester felkér valakit a hallgatóságból, hogy gondoljon egy 1 és 315 közötti számra. Majd így folytatja: Ne árulják el nekem a számot, hanem osszák el öttel és mondják meg a maradékot! Most osszák el héttel és ismét mondják meg nekem a maradékot! Végezetül osszák el kilenccel és mondják meg a maradékot! A játékmester a három maradékból meg tudja határozni az eredeti számot.

Figyeld meg, hogy a három osztó egymáshoz képest relatív prímszám!

A programban szereplő algoritmus csak 1 és 315 közötti számokra működik. A probléma általános megoldása magasabb szintű matematikai ismereteket igényel (pl. egyetem, informatikai képzések)

Maradékos osztás: 7 Mod 2 = 1
Kongruenciák: a ≡ b (mod m) (kiolvasása: a kongruens b-vel modulo m)

A játék algoritmusának mondatszerű leírása:

Program kinaimaradek:

Ki: ”Gondoljon egy 315-nél kisebb számra”    '5x7x9 = 315

Ki: ”Ossza el a számot 5-tel, és adja meg maradékát!”

Be: m5

Ki: ”Ossza el a számot 7-tel, és adja meg maradékát!”

Be: m7

Ki: ”Ossza el a számot 9-cel, és adja meg maradékát!”

Be: m9

szam = (m5*126 + m7*225 + m9*280) Mod 315

Ki: szam

Program vége.