【難関女子中入試】3^2014を30で割った余り

YouTubeでこんな問題を見つけた。

「3を2014回かけた数を30で割ったときの余りを求めなさい」

鷗友（おうゆう）学園女子中学という私立中学の入試問題だ。

この問題を受験生である小学生に解かせるのだから、かなりの難関校だと思う。

同じような問題が灘中でも出題されていた。

【算数】2022年の灘中入試問題（2^2022を17で割った余り）

2022年の灘中の入試問題（算数）がYouTubeで紹介されていたので解いてみた。 問題は「22022を17で割った余り」を求めるとい...

soutai40.com

動画では「合同式で解くのは難しい」と紹介していた。

が、あえて合同式を使って解いてみた。

答案

問題では「3を2014回かけた数」つまり3²⁰¹⁴を30で割っているが、ここでは「3で割る場合」と「10で割る場合」を考える。

「3で割る場合」は、3²⁰¹⁴は当然ながら3で割り切れるから合同式で表すと、

3²⁰¹⁴ ≡ 0 (mod 3)

次に、「10で割る場合」を合同式で表す。

余りをxとすると、

3²⁰¹⁴ ≡ x (mod 10)

3⁴ = 81 ≡ 1 (mod 10) より、

3²⁰¹⁴ = (3⁴)⁵⁰³ × 3² ≡ 1⁵⁰³ × 9 = 9 (mod 10)

a = 3²⁰¹⁴ とおくと、

a ≡ 0 (mod 3) ……①

a ≡ 9 (mod 10) ……②

となる。

30で割った余りを求める

①の両辺を10倍、②の両辺を3倍することで①②を「mod 30」にそろえる。

10a ≡ 0 (mod 30) ……③

3a ≡ 27 (mod 30) ……④

③④をうまく調節して「a ≡ なんとか」にもっていきたい。

④の両辺を3倍すると、

9a ≡ 81 (mod 30) ……⑤

③-⑤より、

a ≡ -81 ≡ -81 + (30 × 3) = -81 + 90 = 9 (mod 30)

よって、求める余りは9。

補足

「a ≡ 9 (mod 10)」の両辺を3倍するとなんで「3a ≡ 27 (mod 30)」になるのか？

理由を説明する。

「a ≡ 9 (mod 10)」とは「aを10で割った余りは9」を意味しているので、

a = 10k + 9 (k: 整数)

とおける。

この両辺を3倍すると、

3a = 3(10k + 9) = 30k + 27

これは「3aを30で割ると余りが27」を表す。

合同式で書き直すと、

3a ≡ 27 (mod 30)

となる。

【2022.10.10追記】簡単な別解

3²⁰¹⁴ ÷ 30 = 3²⁰¹³ ÷ 10

3²⁰¹³ = (3⁴)⁵⁰² × 3 ≡ 3 (mod 10)

より、3²⁰¹³を10で割った余りは3。

式で表すと、

3²⁰¹³ = 10b + 3 (b:正の整数)

両辺を3倍する

3 × 3²⁰¹³ = 3(10b + 3)

3²⁰¹⁴ = 30b + 9

この式は「3²⁰¹⁴を30で割った余りが9」であることを表している。