120＝2^3・3・5の約数は自然数を覆う剰余系を構成する。

x=ai mod(ni)

(ai,ni)

n1＜n2＜・・・、ここではn1=3とする

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

3以上の約数は

3,4,5,6,8,10,12,15,20,24,30,40,60,120

{01,02,03,04,05,06,07,08,09,10}

{11,12,13,14,15,16,17,18,19,20}

{21,22,23,24,25,26,27,28,29,30}

{31,32,33,34,35,36,37,38,39,40}

{41,42,43,44,45,46,47,48,49,50}

{51,52,53,54,55,56,57,58,59,60}

{61,62,63,64,65,66,67,68,69,70}

{71,72,73,74,75,76,77,78,79,80}

{81,82,83,84,85,86,87,88,89,90}

{91,92,93,94,95,96,97,98,99,100}

{101,102,103,104,105,106,107,108,109,110}

{111,112,113,114,115,116,117,118,119,120}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

7以上の素数

7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113

これらは２で割って1余る数ですべて消せるが、2は使ってはならない。すると４で割って1余るもしくは４で割って３余る数ということになる

４で割って1余る→8で割って３余る数

４で割って3余る→8で割って1余る数

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

まず、3と5の倍数を消す

{01,02,04,07,08}

{11,13,14,16,17,19}

{22,23,26,28,29}

{31,32,34,37,38}

{41,43,44,46,47,49}

{52,53,56,58,59}

{61,62,64,67,68}

{71,73,74,76,77,79}

{82,83,86,88,89}

{91,92,94,97,98}

{101,103,104,106,107,109}

{112,113,116,118,119}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

４で割って1余る→8で割って３余る数を消す

{02,04,07,08}

{14,16}

{22,23,26,28}

{31,32,34,38}

{44,46,47}

{52,56,58}

{62,64,68}

{71,74,76,79}

{82,86,88}

{92,94,98}

{103,104,106}

{112,116,118,119}素数は7,23,31,47,71,79,103

7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

４で割って3余る→8で割って1余る数

{02,04,08}

{13,14,16}

{22,26,28,29}

{32,34,37,38}

{44,46}

{52,53,56,58}

{61,62,64,68}

{74,76,77}

{82,86,88}

{92,94,98}

{101,104,106,109}

{112,116,118}素数は13,29,37,53,61,101,109

7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

3,4,5,6,8,10,12,15,20,24,30,40,60,120

４で割って1余る→8で割って３余る数を消す→6で割って1余る数を消す

{02,04,08}

{14,16}

{22,23,26,28}

{32,34,38}

{44,46,47}

{52,56,58}

{62,64,68}

{71,74,76}

{82,86,88}

{92,94,98}

{104,106}

{112,116,118,119}素数は23,47,71→12で割って11余る

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

４で割って3余る→8で割って1余る数→6で割って1余る数を消す

{02,04,08}

{14,16}

{22,26,28,29}

{32,34,38}

{44,46}

{52,53,56,58}

{62,64,68}

{74,76,77}

{82,86,88}

{92,94,98}

{101,104,106}

{112,116,118}素数は29,53,101 →12で割って5余る

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

3,4,5,6,8,10,12,15,20,24,30,40,60,120

４で割って1余る→8で割って３余る数を消す→6で割って1余る数を消す→12で割って11余る数を消す

{02,04,08}

{14,16}

{22,26,28}

{32,34,38}

{44,46}

{52,56,58}

{62,64,68}

{74,76}

{82,86,88}

{92,94,98}

{104,106}

{112,116,118}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

４で割って3余る→8で割って1余る数→6で割って1余る数を消す→12で割って5余る数を消す

{02,04,08}

{14,16}

{22,26,28}

{32,34,38}

{44,46}

{52,56,58}

{62,64,68}

{74,76}

{82,86,88}

{92,94,98}

{104,106}

{112,116,118}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

3,4,5,6,8,10,12,15,20,24,30,40,60,120

４で割って1余る→8で割って３余る数を消す→6で割って1余る数を消す→12で割って11余る数を消す→10で割って4余る数を消す

{02,08}

{16}

{22,26,28}

{32,38}

{46}

{52,56,58}

{62,68}

{76}

{82,86,88}

{92,98}

{106}

{112,116,118}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

４で割って3余る→8で割って1余る数→6で割って1余る数を消す→12で割って5余る数を消す→10で割って4余る数を消す

{02,08}

{16}

{22,26,28}

{32,38}

{46}

{52,56,58}

{62,68}

{76}

{82,86,88}

{92,98}

{106}

{112,116,118} どちらも同じになった

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝