合同式に関する問題です

質問

学校で出た下のような問題が解けないのですがよろしくお願いします。

aは自然数であり、ｐ＝a*a+1 は素数であるとする。この時ｎ*ｎ+1がｐの倍数であるということとn≡a(mod p) もしくは　n≡p-a(mod p) であることは同値である事を示せ。

という問題です。

中二にも分かるレベルで教えていただけると嬉しいです。

回答No.1

alice_44 · ベストアンサー

素数 p に対し、mod p において、
(a^2 ≡ -1 かつ n^2 ≡ -1) ならば (n ≡ a または n ≡ -a)
を示せということですよね。

因数定理より、mod p において、二次方程式 x^2 ≡ -1 の解は最大２個
…で証明になるんじゃないかな？

お礼

ありがとうございます。
ちょっと理解しにくいのですががんばってみます。

回答No.7

alice_44

全く空気を読まない No.1 の続き。

p が素数なら、mod p が体(有限体 Fp)だから、
多項式環 (Fp)[x] がユークリッド整域となって、
因数分解が一意に定まる。よって、
代数方程式の解の個数は、方程式の次数を超えない。

これより、x^2 ≡ -1 の解が２個以下と解かり、
また、式形より、x = a が解ならば x = -a も解だから、
x = a と x = n の両方が x^2 ≡ -1 の解ならば、
n = a または n = -a 以外には無い。

回答No.6

Tacosan

mod p は省略.

※「p が素数なら ab ≡ 0 ⇔ a ≡ 0 または b ≡ 0」
を使っていいなら
n^2 ≡ a^2 ⇔ n^2 - a^2 ≡ 0 ⇔ (n+a)(n-a) ≡ 0
とするのが安全でしょう＞#5.

※を使っちゃダメと言われると.... どこから始めればいいんだろう.

回答No.5

mmk2000

>tacosanさん

そうなんですけど、どこで用いればいいのか分らなかったんですよね。。。
どなたか補足お願いします。

回答No.4

Tacosan

「数学の試験問題に対する解答」として考えるなら, 「p が素数である」ことに触れておかないと減点されても文句は言えないっすよ＞#3.

回答No.3

mmk2000

明らかに中二の域を超えています。
まず、modは高校でも学校では習いません。
あと、「同値である」という表現も高校生じゃないと習いません。

中二といっても、高校レベルの内容を理解している、と判断してもいいんでしょうか？

まず、求める事は
ｎ*ｎ+1がｐの倍数⇔n≡a(mod p) もしくは　n≡p-a(mod p)
を求めれば良いです。
補足として
n≡p-a(mod p)
⇔n-(p-a)=pk (k:自然数)
⇔n+a=p(k+1)
⇔n≡-a(mod p)
とすると、求める問題は
ｎ*ｎ+1がｐの倍数⇔n≡±a(mod p)
となります。
（→）
n^2+1=pk(k:自然数)
n^2≡-1（mod p）
n^2≡p-1(mod p)
条件からp-1=a^2だから
n^2≡a^2(mod p)
よって
n≡±a(mod p)
(←)
n≡±a(mod p)だから
n±a=pk(k:自然数)
n=pk±a
両辺２乗して
n^2=p^2k^2±2pka+a^2
ここでa^2=p-1だから
n^2=p^2k^2±2apk+p-1
n^2+1=p^2k^2±2apk
n^2+1=p(pk^2±2ak)
よってn^2+1はPの倍数。

以上で示せたと思います。

回答No.2

koko_u_u

別にゴチャゴチャ考える必要もなく、普通に式変形すればできるよ。