14n＋52と4n＋17の最大公約数が5になるような50以下の自然数nを求めよ。
解き方が全くわかりません
詳しく教えてください
最大公約数の問題です
フォーラムルール
新規投稿は質問のみとさせていただきます。
新規投稿は質問のみとさせていただきます。
-
ゲスト
Re: 最大公約数の問題です
ご確認をお願いします。
任意の整数a, b (b≠0)に対して、ある整数q, rが存在して、
a=bq+r (0<=r<b)とかける。
この時、aとbの最大公約数をgcd(a, b)と書くと、
gcd(a, b)=gcd(b, r)となる。
これを使います。
14n＋52=3(4n＋17)+2n+1
4n＋17=2(2n+1)+15
したがって、
gcd(14n＋52, 4n＋17)
=gcd(4n＋17, 2n+1)
=gcd(2n+1, 15)
=5
したがって、
2n+1=5m (mは整数)
15=5×3
gcd(2n+1, 15)=5
なので、gcd(m, 3)=1となる。
5m-2n=1なので、
5(m-1)=2(n-2)
gcd(5, 2)=1なので、
m-1=2t, n-2=5t (tは整数)
とかける。つまり、
m=2t+1, n=5t+2 (tは整数)
nは50以下の自然数なので
1<=5t+2<=50
したがって、t=0, 1, 2, 3, 4, 5, 6, 7, 8, 9
となる。この時、
m=1, 3, 5, 7, 9, 11, 13, 15, 17, 19
gcd(m, 3)=1なので、
2t+1=m=1, 5, 7, 11, 13, 17, 19
つまり、
t=0, 2, 3, 5, 6, 8, 9
となる。
つまり、
n=2, 12, 17, 27, 32, 42, 47
任意の整数a, b (b≠0)に対して、ある整数q, rが存在して、
a=bq+r (0<=r<b)とかける。
この時、aとbの最大公約数をgcd(a, b)と書くと、
gcd(a, b)=gcd(b, r)となる。
これを使います。
14n＋52=3(4n＋17)+2n+1
4n＋17=2(2n+1)+15
したがって、
gcd(14n＋52, 4n＋17)
=gcd(4n＋17, 2n+1)
=gcd(2n+1, 15)
=5
したがって、
2n+1=5m (mは整数)
15=5×3
gcd(2n+1, 15)=5
なので、gcd(m, 3)=1となる。
5m-2n=1なので、
5(m-1)=2(n-2)
gcd(5, 2)=1なので、
m-1=2t, n-2=5t (tは整数)
とかける。つまり、
m=2t+1, n=5t+2 (tは整数)
nは50以下の自然数なので
1<=5t+2<=50
したがって、t=0, 1, 2, 3, 4, 5, 6, 7, 8, 9
となる。この時、
m=1, 3, 5, 7, 9, 11, 13, 15, 17, 19
gcd(m, 3)=1なので、
2t+1=m=1, 5, 7, 11, 13, 17, 19
つまり、
t=0, 2, 3, 5, 6, 8, 9
となる。
つまり、
n=2, 12, 17, 27, 32, 42, 47