ここから本文です

【問題】 63^63を62^2で割った余りを求めよ。 【質問】 二項定理で解くと解き...

jar********さん

2020/7/709:31:08

【問題】
63^63を62^2で割った余りを求めよ。

【質問】
二項定理で解くと解きやすいみたいですが、合同式を用いても解けますか?
もし分かる方がいたら教えていただきたいです。

閲覧数:
147
回答数:
4
お礼:
100枚

違反報告

回答

1〜4件/4件中

並び替え:回答日時の
新しい順
|古い順

ran********さん

2020/7/712:17:50

63^63=(62+1)^63≡1+63×62≡63(mod62^2)

jmt********さん

2020/7/710:03:02

二項定理より数倍大変な合同式を使おうというのは勇者なのか無謀なのか…

まあとにかく、できることはできるけど前の方々が書かれてるからそれでいいかな

svi********さん

2020/7/709:54:53

合同式で解くのは難しいと思います。解けるかもしれませんが、すぐに思いつくようなものでもないのでオススメしません。

63^63=(62+1)^63を利用した二項定理の問題なので二項定理で解きます。

(62+1)^63=Σ[k=0→61](63Ck)(62)^(63-k)+63×62+1
なので、63^63を62^2で割った余りは、63×62+1を62^2で割った余りと一致します
63×62+1=(62+1)×62+1
=62^2+63
より、求める答えは63

haj********さん

2020/7/709:53:37

おっしゃる通り、2項定理なら瞬殺ですが、あえて合同式を使うなら、

63≡63 mod(62^2)
63^2≡125 mod(62^2)
63^3≡125*63≡187 mod(62^2)
63^4≡187*63≡249 mod(62^2)

ということで、一般的に、
63^k≡1+62k mod(62^2)
となるので、(証明は帰納法など)

k=63のとき、余りは
62*63+1=3907
しかし、これはまだ62^2で割れるので、実際割ってやると
余りは63である。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる