ここから本文です

53で割ると5余り、61で割ると6余る最小の自然数を求めよ

アバター

ID非公開さん

2019/2/1811:19:18

53で割ると5余り、61で割ると6余る最小の自然数を求めよ

↑を解いてほしいです。できれば解説ものせてほしいです。

閲覧数:
87
回答数:
4

違反報告

ベストアンサーに選ばれた回答

shi********さん

2019/2/1811:47:12

元の数=53m+5=61n+6ということ

53m=61n+1なので
m=(61n+1)/53
={(53+8)n+1}/53
=n+(8n+1)/53 が整数



m=38 n=33

この回答は投票によってベストアンサーに選ばれました!

ベストアンサー以外の回答

1〜3件/3件中

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

hir********さん

2019/2/1811:43:51

N=53a+5=61b+6、となる。

53a=61b+1を解く.
小さい方の係数に着目して、53(a-b)-8b=1、と同値変形する。
a-b=α ‥‥①、とすると、53α-8b=1、になる。

これでも特別解の発見は難しいから、同じことをもう一度やる。

8(6α-b)+5α=1、だから、6α-b=β ‥‥②、とすると
8β+5α=1となって、これの特別解は、(α、β)=(-3、2)、とわかる。
②から、b=6α-β=-20
①から、a=b+α=-23.

この時、53a=61b+1 → 53(a+23)=61(b+20)、になる。
53と61は互いに素から、kを整数として
a+23=61k、b+20=53k ‥‥③、である。
從って、N=53a+5=61b+6=③から=3233k-1214、になる。

これが自然数だから、3233k-1214≧1 → k≧1
よって、k=1で最小だから、N=3233k-1214=2019.

ari********さん

2019/2/1813:58:45

x≡5 (mod 53)、x≡6 (mod 61)
gcm(53,61)=1、逆元 a, b を用いて解を表す。

61a≡1 (mod 53)
8a≡1+3*53≡160
gcm(8,53)=1 ゆえ 8 で割ると、
a≡20 (mod 53)

53b≡1 (mod 61)
ー8b≡1+3*61≡184
gcm(8,61)=1 ゆえ ー8 で割ると、
b≡ー23 (mod 61)

x≡61*a*5+53*b*6≡ー1214≡2019 (mod 53*61)
x≡2019 (mod 3233) → x=3233*n+2019
最小の自然数:x は n=0 のときで x=2019。

vbo********さん

2019/2/1816:33:53

求める数:N
とすると、題意より
N=53a+5=61b+6…(a,b:整数)…①
と置ける
上記式の中間と右辺より
53a+5=61b+6
53a-61b=1…②
②の特殊解をユークリッド互除法で探す
61=53+8⇒8=61-53…③
53=8*6+5⇒5=53-8*6…④
8=5+3⇒3=8-5…⑤
5=3+2⇒2=5-3…⑥
3=2+1⇒1=3-2…⑦

⑦を再掲
1=3-2
ここに⑥を代入
=3-(5-3)
=3*2-5
ここに⑤を代入
=(8-5)*2-5
=8*2-5*3
ここに➃を代入
=8*2-(53-8*6)*3
=8*20-53*3
ここに③を代入
=(61-53)*20-53*3
=61*20-53*23
再度記載し、ユークリッドの互除法より
53*(-23)-61*(-20)=1…⑧
という②の特殊解を得る
②-⑧
53(a+23)-61(b+20)=0
53(a+23)=61(b+20)…⑨
53と61は互いに素なので
b+20=53k…(k:整数)…⑩
と置くことができる
b=53k-20…⑪
⑩を①に代入し
N=61b+6=61(53k-20)+6=3233k-1214…(k:整数)…⑫
Nは自然数だから
N=61b+6=61(53k-20)+6=3233k-1214≧1…⑬
⑬から
k≧1215/3233
であり、kは整数だから
k≧1…⑭
つまり、最小となるのは、k=1の時だから
N=3233-1214=2019…答

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

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

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

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

閉じる

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

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

閉じる