18480：2^6754≡？ (mod 1155)

問題18480・・・http://www.geocities.jp/ikuro_kotaro/koramu/8326_t5.htm より 引用 Orz〜

2^6754＝？　　（mod 1155）

解答

・上記サイトより Orz〜

１１５５＝３・５・７・１１

フェルマーの小定理より

　　２^2＝１　　（ｍｏｄ３）

　　２^4＝１　　（ｍｏｄ５）

　　２^6＝１　　（ｍｏｄ７）

　　２^10＝１　　（ｍｏｄ１１）

したがって，

　　２^6754＝１　　（ｍｏｄ３）

　　２^6754＝４　　（ｍｏｄ５）・・・6754/4=1688...2, 2^2=4

　　２^6754＝２　　（ｍｏｄ７）・・・6754/6=1125...4,2^4=2

　　２^6754＝５　　（ｍｏｄ１１）・・・6754/10=...4,2^4=5

こうして，連立合同式

［１］ｘ＝１　　（ｍｏｄ３）

［２］ｘ＝４　　（ｍｏｄ５）

［３］ｘ＝２　　（ｍｏｄ７）

［４］ｘ＝５　　（ｍｏｄ１１）

が得られる．

［１］ｘ＝１＋３ｙ

［２］１＋３ｙ＝４　　（ｍｏｄ５）→ｙ＝１　　（ｍｏｄ５）

→ｙ＝１＋５ｚ→ｘ＝１＋３ｙ＝４＋１５ｚ

［３］４＋１５ｚ＝２　　（ｍｏｄ７）→ｚ＝５　　（ｍｏｄ７）

→ｚ＝５＋７ｔ→ｘ＝７９＋１０５ｔ

［４］７９＋１０５ｔ＝５　　（ｍｏｄ１１）→ｔ＝６　　（ｍｏｄ１１）

→ｔ＝６＋１１ｕ→ｘ＝７０９＋１１５５ｕ

［Ａ］２^6754＝７０９　　（ｍｏｄ１１５５）

*意外と面倒ね ^^;