整数論の問題

方針：位数は $\phi (29)$ の約数であることを使い、約数だけを調べる。

$29$ は素数なので $\phi (29)=28$ である。$\gcd (5,29)=1$ だから、フェルマーの小定理より
$$5^{28}\equiv 1(\mathrm{mod}29)$$
が成り立つ。

位数 $d={\mathrm{ord}}_{29}(5)$ について「$5^k\equiv 1(\mathrm{mod}29)⟺d\mid k$」が成り立つので、$d\mid 28$ である。よって $d$ の候補は $28$ の約数
$$1,2,4,7,14,28$$
だけである。小さい順に調べる。

• $5^1=5\not\equiv 1$
• $5^2=25\equiv -4(\mathrm{mod}29)$ なので $5^2\not\equiv 1$
• $5^4=(5^2{)}^2\equiv (-4{)}^2=16(\mathrm{mod}29)$ なので $5^4\not\equiv 1$
• $5^7=5^4\cdot 5^2\cdot 5\equiv 16\cdot (-4)\cdot 5=-320(\mathrm{mod}29)$。$320=29\times 11+1$ より $-320\equiv -1(\mathrm{mod}29)$。よって $5^7\equiv -1\not\equiv 1$
• $5^{14}=(5^7{)}^2\equiv (-1{)}^2=1(\mathrm{mod}29)$

したがって、$1,2,4,7$ では $1$ にならず、$14$ で初めて $1$ になるから
$${\mathrm{ord}}_{29}(5)=14$$
である。

フェルマーの小定理より $5^{28}\equiv 1(\mathrm{mod}29)$ なので、位数は $28$ の約数 $1,2,4,7,14,28$ のいずれかである。

$5^1=5$、$5^2=25$ である。
$5^4=25^2=625=29\cdot 21+16$ より $5^4\equiv 16$ である。
$5^7=5^4\cdot 5^2\cdot 5\equiv 16\cdot 25\cdot 5$ である。ここで $16\cdot 25=400=29\cdot 13+23$ より $400\equiv 23$。さらに $23\cdot 5=115=29\cdot 4-1$ より $115\equiv -1\equiv 28$。よって $5^7\equiv -1$ である。

したがって $5^{14}\equiv (-1{)}^2=1$ である。

$5^7\equiv -1\ne 1$ なので、位数は $7$ ではない。位数は $14$ の約数だから $1,2,7,14$ のいずれかである。$5^1\equiv 5$、$5^2\equiv 25$、$5^7\equiv -1$ はいずれも $1$ ではない。よって位数は $14$ である。

検算：$5^{14}\equiv 1$ であり、$14$ の真の約数 $1,2,7$ では $1$ にならない。また $28$ の約数 $4$ も、位数が $14$ の約数であることから候補にならない（$5^4\equiv 16\ne 1$ でもある）。