この問題が全く分からないです。
教えて下さい、宜しくお願いします。
![]() |
No.76771 - 2021/07/19(Mon) 09:29:29
| ☆ Re: 情報解析学 / WIZ | | | 記号「¬≡」は「不合同」の意味とします。
n が合成数であると仮定して矛盾を導きます。
前提条件
(A) 整数 a, n は共に 1 より大きいとする。
(B) a^(n-1) ≡ 1 (mod n)
(C) n-1 の任意の(正の)約数 m (ただし m ≠ n-1) に対して a^m ¬≡ 1 (mod n)
先ず、n-1個の自然数 {a^1, a^2, ・・・, a^(n-1)} は法 n で全て不合同であることを証明します。
自然数 i, j が 1 ≦ i < j ≦ n-1 であるとき、a^i ≡ a^j (mod n) だったと仮定します。
1 ≦ j-i < n-1 で a^(j-i) ≡ 1 (mod n) となります。
e[1] = j-i とおくと、(C)より e[1] は n-1 の約数ではありません。
従って、ある自然数 k[1] が存在して、k[1]e[1] < n-1 < (k[1]+1)e[1] となります。
e[1] > 1 ならば、a^e[1] ≡ 1 (mod n) かつ(B)より、
a^((n-1)-k[1]e[1]) = (a^(n-1))((a^e[1])^(-k[1])) ≡ 1 (mod n) です。
e[2] = (n-1)-k[1]e[1] とおくと、e[2] < e[1] かつ a^e[2] ≡ 1 (mod n) であり、
(C)より e[2] も n-1 の約数ではありません。
e[2] > 1 ならば、同様に k[2]e[2] < n-1 < (k[2]+1)e[2] となる自然数 k[2] が存在して、
e[3] = (n-1)-k[2]e[2] < e[2] かつ a^e[3] ≡ 1 (mod n) とでき、
以下、e[1] > e[2] > e[3] > ・・・ e[x] = 1 と減少する数列を構成できます。(x は自然数)
e[x] = 1 は(C)と矛盾します。
また e[x-1] > 1 かつ e[x] = 0 と 1 を飛び越えて減少することもありません。
何故なら、e[x] = 0 = (n-1)-k[x-1]e[x-1] と e[x-1] が n-1 の約数となり(C)と矛盾しているからです。
以上から、 1 ≦ i < j ≦ n-1 であるとき、a^i ≡ a^j (mod n) だったという仮定が誤りで、
{a^1, a^2, ・・・, a^(n-1)} は法 n で全て不合同で、
剰余類としては {1, 2,・・・, n-1} を並び変えただけのものと言えます。
つまり、
Π[k = 1, n-1](a^k) ≡ Π[k = 1, n-1]k (mod n)
⇒ a^((n-1)n/2) ≡ (n-1)! (mod n) ・・・・・(D)
次に n が 4 以外の合成数ならば、(n-1)! は n で割り切れることを示します。
n = 4 に対して題意を満たす a が存在しないことは容易に示せると思うので省略します。
自然数 p, q が 1 < p < q で n = pq の場合、1 < p < q < n となるので、
p と q は 1, 2, ・・・, n-1 の異なるどれかと一致しますので、(n-1)! は pq で割り切れます。
自然数 p が 1 < p で n = p^2 の場合、n ≠ 4 なので p > 2 で、1 < p < 2p < p^2 = n となるので、
p と 2p は 1, 2, ・・・, n-1 の異なるどれかと一致しますので、(n-1)! は p*2p で割り切れます。
つまり、(n-1)! は p^2 でも割り切れます。
以上から、 n が 4 以外の合成数ならば (n-1)! ≡ 0 (mod n) となりますが、
a^((n-1)n/2) ¬≡ 0 (mod n) なので、(D)は矛盾です。
従って、n が(4以外の)合成数ならば題意は成立しません。
素数に関する原始根の存在とその性質を既知とすれば、(A)より n は素数といえます。
# n = 2 は素数ですが、題意を満たしていると言えるのかは微妙ですが。
|
No.76819 - 2021/07/20(Tue) 16:47:26 |
| ☆ Re: 情報解析学 / 高校三年生 | | | 混乱してきた。整理すると、
?@「aの素因数にnの素因数がスッポリ入るとき」→「aの塁乗数でいずれは割れる。a^(n-1)ならより確実。」
?A「aの素因数にないものがnの素因数にあるとき」→「aの塁乗数では割れない。」
?Aについてさらに分割すると、
[?@]「nが素数のとき」→「aの塁乗数の余りは、n-1通りのすべてを取り得る。ひと回りするまで重複しない。」
[?A]「nが合成数のとき」→「aの塁乗数の余りには、取り得ない数が存在する。ひと回りするまでに重複する。」
こんな感じですか？
しかし、[?A]のケースでたまたま、
a^(n-1) ≡ 1 (mod n)
が取り得て、かつ重複しない余りという可能性はないのかな？
合成数の場合の余り方のパターンを詳しく知りたいな。
|
No.76825 - 2021/07/20(Tue) 23:10:22 |
| ☆ Re: 情報解析学 / 高校三年生 | | | あっ！高校数学範囲だ。
東大入試で出てもおかしくない。
{a,a^2,・・・,a^(n-1)}のうち、合同なものが少なくとも１組存在するなら、
0<i<j<nを満たす整数組(i,j)に対し、
a^i・{a^(j-i) - 1}≡0 (mod n)かつ
a^i ¬≡0 (mod n)
を満たすものが存在し、そのとき{a,a^2,・・・,a^(n-2)}のうち、余りが1となるものが少なくとも一つは存在する。
これは題意を満たさないので、{a,a^2,・・・,a^(n-1)}の余りは、相異なるn-1通りの余りをもつ。
また、題意より、0<k<nを満たす整数kに対し、
a^(ℓ(n-1)+k)≡a^k・{a^(n-1)}^ℓ≡a^k (mod n)(ℓ=1,2・・・)
なので、連続するn-1個のaの塁乗数を元とする集合Uℓを、
Uℓ = {a^(ℓ(n-1)+1),a^(ℓ(n-1)+2),・・・,a^((ℓ+1)(n-1))} (ℓ=0,1,2・・・)
と定めると、結局、
Uℓ≡{1,2,・・・,n-1} (mod n)(ℓ=0,1,2・・・)
となり、
Π[k = 1, n^2-1](a^k) ≡ Π[k = 1, n-1]k^(n+1) (mod n)
⇒ a^((n^2-1)n^2/2) ≡ [(n-1) !]^(n+1) (mod n)
ここで、nを合成数と仮定しても、重複する素因数の個数は、高々n/2以下なので、
共に1でないnの約数pとqに対して、
n = pq ⇒ {p,q}⊆{1,2,・・・,[(n-1) !]^(n+1)}
よって、
[(n-1)!]^(n+1)≡0 (mod n)
⇒ a^((n^2-1)n^2/2) ≡0 (mod n)
⇒ {a^(n-1)}^((n+1)n^2/2) ≡0 (mod n)
これは題意に矛盾。結局、nは素数。
|
No.76832 - 2021/07/21(Wed) 09:02:25 |
| ☆ Re: 情報解析学 / WIZ | | | 高校三年生さんへ
> しかし、[?A]のケースでたまたま、
>
> a^(n-1) ≡ 1 (mod n)
>
> が取り得て、かつ重複しない余りという可能性はないのかな？
自然数 n が合成数で、n と互いに素である任意の整数 a に対して a^(n-1) ≡ 1 (mod n)
となる n は存在し、カーマイケル数と呼ばれています。
しかし、「重複しない余りという可能性」はありません。
何故なら、a が n と互いに素なので、a の累乗も n と互いに素であり、
法 n の零因子(n と互いに素でない整数)と a の累乗が合同になることはないからです。
# 自然数 u, v が 1 < u < n, 1 < v < n, n = uv だったとして、
# 自然数 s, t に対して、a^s ≡ u (mod n) つまり a^s = u+tn = u(1+tv) となるが、
# (a, uv) = 1 より (a^s, u) = 1 なので矛盾。
オイラーの定理 (a, n) = 1 ならば a^(φ(n)-1) ≡ 1 (mod n) を調べてみると良いでしょう。
> を満たすものが存在し、そのとき{a,a^2,・・・,a^(n-2)}のうち、余りが1となるものが少なくとも一つは存在する。
> これは題意を満たさないので、{a,a^2,・・・,a^(n-1)}の余りは、相異なるn-1通りの余りをもつ。
題意は「n-1 の任意の(正の)約数 m (ただし m ≠ n-1) に対して a^m ¬≡ 1 (mod n)」なので、
余りが1となる a の指数が n-1 の約数でないのなら、直ちに「題意を満たさない」とは言えないですよね?
というか、上記が矛盾である(題意を満たさない)ことを証明するのが、この問題のキモなんだと思います。
なので、私の解法では余りが1となる a の指数が n-1 の約数ではないとことから、
ユークリッドの互助法的に a の指数を小さくしていって、最後は指数が 1 になり、
n-1 の約数である 1 が指数となったという矛盾を導いている訳です。
> 共に1でないnの約数pとqに対して、
>
> n = pq ⇒ {p,q}⊆{1,2,・・・,[(n-1) !]^(n+1)}
p = q ならば {p, q} ⊆ {1,2,・・・,[(n-1) !]^(n+1)} とは言えないのでは?
(n が素数の2乗で、1より大きい異なる2個の自然数の積に表せない場合)
おそらく、p < 2p < [(n-1) !]^(n+1) だから、
{p, 2p} ⊆ {1,2,・・・,[(n-1) !]^(n+1)} と間接的に示すことになるのでは?
|
No.76838 - 2021/07/21(Wed) 12:46:09 |
| ☆ Re: 情報解析学 / 高校三年生 | | | WIZ さん、返信ありがとうございます。
>オイラーの定理 (a, n) = 1 ならば a^(φ(n)-1) ≡ 1 (mod n) を調べてみると良いでしょう。
なるほど。調べてみます。
>直ちに「題意を満たさない」とは言えないですよね?
仰るとおりです。(T_T)
>p = q ならば {p, q} ⊆ {1,2,・・・,[(n-1) !]^(n+1)} とは言えないのでは?
情け無いです。この式自体、大嘘ですね。書くなら、
p = q ならば {p, q} ⊆ {φ｜φは「（n-1以下の素因数）の塁乗数」同士の積で表せる[(n-1) !]^(n+1)以下の整数}
こんな感じじゃないと。これなら、どんな素因数に対しても、少なくともn+1個以上は含まれますので。
ところで、n が素数の2乗なら、上式の右辺の元になるのではないでしょうか？
やばいのは、n=2^k の場合ですが、それでもkは高々n/2以下かと。
|
No.76840 - 2021/07/21(Wed) 14:41:06 |
| ☆ Re: 情報解析学 / WIZ | | | 高校三年生さんへ
実は、76832の書き込みの
> また、題意より、0<k<nを満たす整数kに対し、
以降とか、
76840の書き込みの
> p = q ならば {p, q} ⊆ {φ｜φは「（n-1以下の素因数）の塁乗数」同士の積で表せる[(n-1) !]^(n+1)以下の整数}
以降は、私にとって殆ど意味不明です。
特に、上記の「素因数」はどの整数の素因数ですか? n の? n-1 の? (n-1)! の? それ以外?
本問題の私や高校三年生さんの解法のアウトラインは、
(1) n が4以外の合成数であると仮定すると、
題意の a に対して {a^1, a^2, ・・・, a^(n-1)} は法 n の 0 以外の代表剰余類となる。
Π[k = 1, n-1](a^k) ≡ (n-1)! (mod n) となるが、右辺は 0 に合同で、左辺は 0 に不合同なので矛盾。
だから n は合成数ではない。
(2) n が素数ならば題意が満たされることを示す。
・・・となります。
私の解説では、(2)については素数の原始根の性質から示せるとだけ書いていて、詳細は述べていません。
真面目にやろうとすると、原始根の存在証明をすることになり厄介(!)ですからね。
但し、高校三年生さんの「n を合成数と仮定すると矛盾するから n は素数だ!」みたいな早とちりはだめですよ。
n が素数でも題意を満たさないかもしれないし、題意を満たすというなら、それを証明しないといけません。
もうひとつ、集合の包括関係に対する誤解があるように思えます。
通常の集合(set)は同一の要素を重複して含みません。
プログラミング言語なら、同一の要素を重複して含む多重集合(multiset)というのがありますが。
「p = q ならば {p, q} ⊆ {φ｜φはナンタラ・・・}」の集合 {φ｜φはナンタラ・・・} は重複した整数を含みませんよね?
なので、上記の包括関係は成立しません。
それとも、高校三年生さんは {2, 2} ⊆ {1, 2, 3, 4, 5} と思っているのですか?
失礼しました。
|
No.76845 - 2021/07/21(Wed) 21:14:22 |
| ☆ Re: 情報解析学 / 高校三年生 | | | WIZ さん、返信ありがとうございます。
> {2, 2} ⊆ {1, 2, 3, 4, 5} と思っているのですか?
いえ、思ってません。
WIZ さんの解法は理解しているつもりです。
{2, 2} ⊆ {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}
これは成立しますよね？
a^(n(n-1)/2)はとても小さな値で、余りをたった「一巡」しかできません。
具体例）
n=4
a・a^2・a^3≡1・2・3≡2 (mod n)
a・a^2・a^3・a^4・a^5・a^6≡1・2・3・1・2・3≡0 (mod n)
２巡目で割り切れました。a^21 について、集合表記で、
{n}⊆{1, 2, 3, 2^2, 6, 3^2, 12 ,18, 36}
です。右辺は「（3以下の素因数）の塁乗数」同士の積で表せる36以下の整数です。
|
No.76848 - 2021/07/22(Thu) 02:57:13 |
|
