ここで勉強すれば数学検定１級の壁は超えられるか。

 

 

 

 

$2013^{22}÷25$の余りを求める。

 

 

 

 

 

 

$a^{\varphi \left( n\right) }\equiv 1\left( mod　n\right)$

 

 

a＝２０１３，ｎ＝２５＝５×５に対してオイラー関数

 

 

 

$\varphi \left( 25\right) = 25\left( 1-\dfrac {1}{5}\right)= 20$

 

 

 

だから

 

 

$2013^{20}\equiv 1\left( mod25\right)$が求まる。

 

 

 

$2013^{22}=2013^{20}\cdot 2013^{2}\equiv 2013^{2}$　

 

 

 

$=\left( 2000+13\right) ^{2}=2000^{2}+2\cdot 13\cdot 2000+13^{2}$

 

 

 

$\equiv 13^{2}\left( mod25\right) =169\left( mod25\right) \equiv　19\left( mod25\right)$

 

 

 

$19$・・・答え

 

 

 

参考事項

 

オイラーの定理

 

 

 

 

ｐ，ｑ，ｒは素数であるとき

 

 

$n=p^{a}\cdot q^{b}\cdot r^{c}\Rightarrow \varphi \left( n\right) =n\left[ \left( 1-\dfrac {1}{p}\right) \left( 1-\dfrac {1}{q}\right) \left( 1-\dfrac {1}{r}\right) \right]$

 

 

 

上記のようにオイラー関数の値が求まる。

 

 

 

 

自然数ｎとaに対して、aとｎがお互い素であるとき、オイラーの定理より

 

 

 

 

$a^{\varphi \left( n\right) }\equiv 1\left( mod　n\right)$になる。