プロが教えるわが家の防犯対策術!

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

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

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

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

です。お願いします。

教えて!goo グレード

A 回答 (5件)

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を含むことはない。
    • good
    • 1
この回答へのお礼

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

お礼日時:2007/09/11 22:49

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

    • good
    • 0
この回答へのお礼

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

お礼日時:2007/09/11 22:57

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



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)は整数解を持ちません。
    • good
    • 0
この回答へのお礼

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

お礼日時:2007/09/11 22:56

解をもてば,


x^2 = 100n+35
とあらわせる.
つまり,
x^2 = 5(20n+7)
つまり,x^2は5の倍数.
つまり,x^2は25の倍数でもある.
つまり,20n+7は5の倍数.
しかし,
20n+7=5(4n+1)+2
で5で割り切れない.
よって矛盾.
    • good
    • 0
この回答へのお礼

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

お礼日時:2007/09/11 22:53

こんにちは。



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

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

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

お礼日時:2007/09/11 22:51

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

教えて!goo グレード

人気Q&Aランキング