$n$を$2$以上の自然数とします｡ そして \[1+2+\cdots +(n-1) \pmod{n} \tag{*}\] を考察します｡
1. Pythonを用いて, $n$に$2$から$20$までの各整数を当てはめて, 上の式(*)を計算してください｡ そこからどのような法則が成立しそうか予想してください｡
2. (1)の予想を証明してください｡
まずは自然数$1$から$k$までの総和を求める関数を書きます｡
def sum_of_first_k(k):
sum = 0 # これが総和になる
for i in range(1,k+1): # k+1は含まれないことに注意
sum += i
return sum
次に, 合同式の計算には%を使うことを思い出しましょう｡ 式(*)の和は$n-1$までということに注意するとPythonコードは次のようになります｡
for i in range(2,21):
print(f"n={i}のときの(*): {sum_of_first_k(i-1) % i}")
n=2のときの(*): 1
n=3のときの(*): 0
n=4のときの(*): 2
n=5のときの(*): 0
n=6のときの(*): 3
n=7のときの(*): 0
n=8のときの(*): 4
n=9のときの(*): 0
n=10のときの(*): 5
n=11のときの(*): 0
n=12のときの(*): 6
n=13のときの(*): 0
n=14のときの(*): 7
n=15のときの(*): 0
n=16のときの(*): 8
n=17のときの(*): 0
n=18のときの(*): 9
n=19のときの(*): 0
n=20のときの(*): 10
この結果から$n$が奇数のときには(*)は$0$となり, $n$が偶数のときには(*)は$n/2$となると予想できます｡
では(1)で予想した｢$n$が奇数のときには(*)は$0$となり, $n$が偶数のときには(*)は$n/2$となる｣を証明します｡
式(*)は和の公式を用いると \[\frac{(n-1)n}{2} \pmod{n}\] と書けます｡
まず, $n$が奇数の場合を考えます｡ このとき$\frac{n-1}{2}$が自然数になるので$\frac{(n-1)n}{2}=\frac{n-1}{2}\cdot n$は$n$の倍数になることから \[\frac{(n-1)n}{2}\equiv 0 \pmod{n}\] となり予想通りとなります｡
次に, $n$が偶数の場合を考えます｡ このときは$\frac{n}{2}$が自然数になるので \begin{align*} \frac{(n-1)n}{2} &\equiv (n-1)\frac{n}{2} \pmod{n}\\ &\equiv (-1)\frac{n}{2} \pmod{n}\\ &\equiv n-\frac{n}{2} \pmod{n}\\ &\equiv \frac{n}{2} \pmod{n} \end{align*} となり予想通りの$n/2$を得ました｡