Fussy's Diary

今日は鏡開き。ということで、昼はぜんざいを食べました。

鏡餅は鏡開きの日に食べるわけですが、昔は固くなった餅を割って食べたのでずいぶんと硬かった思い出があります。今では餅がパックに入ったものが売られているので餅が硬くなることもなく、しかも取り出して調理するだけで済むというのは便利な世の中になったものだと思います。
餅を使った料理というと、雑煮・ぜんざい・焼き餅くらいが定番でしょうか。「餅 レシピ」でググってみたら、オニオンスープとチーズでグラタン風にしたり、ホットケーキに入れたり、牛乳やココアと合わせてみたりといろんなレシピが見つかりました。こういうアイデアが浮かぶというのはすごいものだと思います。

さて、今回は「数学問題bot」のこんな問題を解いてみました。

-----

1) 自然数 n を 2 つの自然数 p, q の和 ( n = p + q ) に分解した時、常に p, q が互いに素であるならば、n は素数であることを示せ。
2) 1000を 2 つの互いに素な自然数の和に分解する方法は何通りか。ただし和の順番を入れ替えたものは同じとみなす。( nyoki1007 様 )

1) n が合成数ならば、2 以上の二つの因数 k, m に分解できるので、m = p' + q' とすれば

n = km = k( p' + q' ) = kp' + kq'

と表すことができます。従って、p = kp', q = kq' とすれば、互いに素でない二つの数 p, q の和で表すことができます。

従ってその対偶として、常に p, q が互いに素ならば n は素数であることになります。

2) 合成数 N が素因数 p1^r1p2^r2 ... pm^rm ( rk ( k = 1, 2, ... m ) > 0 ) に分解できるとします。N > L を満たす L が N の中の素因数で構成され、

L = p1^s1p2^s2 ... pm^sm・Q ( sk ≥ 0 )

で表されるならば、rk, sk のうち最小値を tk として

N - L = p1^t1p2^t2 ... pm^tm( p1^r1-t1p2^r2-t2 ... pm^rm-tm - p1^s1-t1p2^s2-t2 ... pm^sm-tmQ )

となります。p1^t1p2^t2 ... pm^tm は L も共有する因数なので、N - L と L は互いに素ではない数であり、その和は N になります。逆に、L が N と共通な因数を一つも持たなければ、N - L とも共通の因子を持たないことになり、L と N - L は互いに素になります。

1000 = 2³5³ なので、素因数として 2 と 5 を持ちます。1 から 500 の間で素因数 2 を持つ数は 250 個、5 を持つ数は 100 個あります。しかし、2, 5 の両方を持つ数は 10 の倍数で 50 個あるので、2, 5 のいずれかを素因数に持つ数は 250 + 100 - 50 = 300 個あります。よって、500 - 300 = 200 個の数は 2, 5 のいずれも素因数として持たず、この数との和が 100 になる組み合わせ全てが互いに素になります。従って、答えは 200 個になります。