x^2 = 35(mod 100)は解を持たない

質問

練習問題を解いていたのですが、解答が

「解を持てば矛盾を示せばよい」

とだけあって、どのように解くか、取っ掛かりがわかりません。
問題は

x^2 = 35(mod 100)は解を持たないことを照明せよ。

です。お願いします。

回答No.1

zk43 · ベストアンサー

x^2 = 35(mod 100)
から、
x^2=35+100n=5(7+20n)
となる。
右辺が平方数になるには、7+20nが素因数5を奇数個含まなければならない。
しかし、7+20n=2+5+20n=2+5(1+4n)だから、これは5で割ると2余り、素
因数5を含むことはない。

お礼

ありがとうございます。
何かの定理を適用するのだと思い込んでしまって、はまってしまいました。助かりました。

回答No.5

katadanaoki

平方剰余の相互法則 を使えばいいだけでは？

お礼

ありがとうございます。
皆さんのおかげで理解できました。

回答No.4

yoikagari

こんな感じで証明します。

x^2≡35　(mod　100)が整数解を持つと仮定します。
x^2=35+100k=5×(7+20k)・・・●
(ただしx,kは整数)
●より、x^2が5で割り切れます。
5は素数だから、xは5で割り切れます。
x=5y(yは整数)と書けます。
25*y^2=35+100k
5y^2=7+20k
5y^2-20k=7
y^2-4k=7/5・・・◎
◎の左辺は整数ですが、右辺は整数ではないので不合理です。

以上よりx^2≡35　(mod　100)は整数解を持ちません。

お礼

ありがとうございます。
よく納得できました。自分の基礎力をもっと付けたいと思います。
助かりました。

回答No.3

montmort

解をもてば，
x^2 = 100n＋35
とあらわせる．
つまり，
x^2 = 5（20n＋7）
つまり，x^2は5の倍数．
つまり，x^2は25の倍数でもある．
つまり，20ｎ+7は5の倍数．
しかし，
20n+7=5（4n+1)+2
で5で割り切れない．
よって矛盾．

お礼

ありがとうございます。
こんなに多くご解答いただけるとは思っておらず
恐縮です。No.1の方にちかい解きかたですね。
助かりました。

回答No.2

ka1234

こんにちは。

x^2≡35(mod100)　となることはないんですよ。25になる場合はあるけど。

1　問題文の読解。「ｘを２乗したら、下２桁が３５になる」と読める。
2　すると必要条件として、「一の位は５である」となる。
　（他の数字であれば２乗して一の位が５にはならない）
3　すると、x＝10a＋5（aは自然数）とおける。
4　x^2＝(10a+5)^2＝100a^2+100a+25
　　　　　　　　　　　≡25(mod100)
5　mod100で25≡35ではないから、問題の方程式は解を持たない。（証明終わり）

お礼

ありがとうございます。
最後の5が合同式の問題っぽくていい感じがしました(^^)
助かりました。