(1) $7n+6$ と $3n+4$ の最大公約数が5となるような、2桁の自然数 $n$ をすべて求めよ。 (2) $4n+15$ と $3n+13$ の最大公約数が7となるような、50以下の自然数 $n$ をすべて求めよ。 (3) $6n+9$ と $5n+8$ が互いに素となるような、100以下の自然数 $n$ は何個あるか。

1. 問題の内容

(1) $7n+6$ と $3n+4$ の最大公約数が5となるような、2桁の自然数 $n$ をすべて求めよ。

(2) $4n+15$ と $3n+13$ の最大公約数が7となるような、50以下の自然数 $n$ をすべて求めよ。

(3) $6n+9$ と $5n+8$ が互いに素となるような、100以下の自然数 $n$ は何個あるか。

2. 解き方の手順

(1)

$7n+6$ と $3n+4$ の最大公約数が5であることから、$7n+6$ も $3n+4$ も5の倍数である。

$7n+6 \equiv 0 \pmod{5}$ より、

$2n+1 \equiv 0 \pmod{5}$

$2n \equiv -1 \equiv 4 \pmod{5}$

$n \equiv 2 \pmod{5}$

よって、$n = 5k+2$ ($k$ は整数) と表せる。

同様に、$3n+4 \equiv 0 \pmod{5}$ より、

$3n \equiv -4 \equiv 1 \pmod{5}$

$6n \equiv 2 \pmod{5}$

$n \equiv 2 \pmod{5}$

よって、$n = 5k+2$ ($k$ は整数) と表せる。

$n$ が2桁の自然数であるから、$10 \le n \le 99$。

$10 \le 5k+2 \le 99$

$8 \le 5k \le 97$

$1.6 \le k \le 19.4$

$k$ は整数なので、$2 \le k \le 19$。

したがって、$n=5k+2$ は $5(2)+2=12$ から $5(19)+2=97$ まで。

$7n+6=7(5k+2)+6=35k+20=5(7k+4)$

$3n+4=3(5k+2)+4=15k+10=5(3k+2)$

$7k+4$と$3k+2$が互いに素である必要がある。

$7k+4$ と $3k+2$ の最大公約数が1となるような $k$ を探す。

$k=2$のとき $n=12$, $7k+4=18$, $3k+2=8$, gcd(18,8)=2

$k=3$のとき $n=17$, $7k+4=25$, $3k+2=11$, gcd(25,11)=1

$k=4$のとき $n=22$, $7k+4=32$, $3k+2=14$, gcd(32,14)=2

$k=5$のとき $n=27$, $7k+4=39$, $3k+2=17$, gcd(39,17)=1

$k=6$のとき $n=32$, $7k+4=46$, $3k+2=20$, gcd(46,20)=2

$k=7$のとき $n=37$, $7k+4=53$, $3k+2=23$, gcd(53,23)=1

$k=8$のとき $n=42$, $7k+4=60$, $3k+2=26$, gcd(60,26)=2

$k=9$のとき $n=47$, $7k+4=67$, $3k+2=29$, gcd(67,29)=1

$k=10$のとき $n=52$, $7k+4=74$, $3k+2=32$, gcd(74,32)=2

$k=11$のとき $n=57$, $7k+4=81$, $3k+2=35$, gcd(81,35)=1

$k=12$のとき $n=62$, $7k+4=88$, $3k+2=38$, gcd(88,38)=2

$k=13$のとき $n=67$, $7k+4=95$, $3k+2=41$, gcd(95,41)=1

$k=14$のとき $n=72$, $7k+4=102$, $3k+2=44$, gcd(102,44)=2

$k=15$のとき $n=77$, $7k+4=109$, $3k+2=47$, gcd(109,47)=1

$k=16$のとき $n=82$, $7k+4=116$, $3k+2=50$, gcd(116,50)=2

$k=17$のとき $n=87$, $7k+4=123$, $3k+2=53$, gcd(123,53)=1

$k=18$のとき $n=92$, $7k+4=130$, $3k+2=56$, gcd(130,56)=2

$k=19$のとき $n=97$, $7k+4=137$, $3k+2=59$, gcd(137,59)=1

$n = 17, 27, 37, 47, 57, 67, 77, 87, 97$

(2)

$4n+15$ と $3n+13$ の最大公約数が7であることから、$4n+15$ も $3n+13$ も7の倍数である。

$4n+15 \equiv 0 \pmod{7}$ より、

$4n+1 \equiv 0 \pmod{7}$

$4n \equiv -1 \equiv 6 \pmod{7}$

$8n \equiv 12 \pmod{7}$

$n \equiv 5 \pmod{7}$

よって、$n = 7k+5$ ($k$ は整数) と表せる。

同様に、$3n+13 \equiv 0 \pmod{7}$ より、

$3n-1 \equiv 0 \pmod{7}$

$3n \equiv 1 \pmod{7}$

$6n \equiv 2 \pmod{7}$

$-n \equiv 2 \pmod{7}$

$n \equiv -2 \equiv 5 \pmod{7}$

よって、$n = 7k+5$ ($k$ は整数) と表せる。

$n$ が50以下の自然数であるから、$1 \le n \le 50$。

$1 \le 7k+5 \le 50$

$-4 \le 7k \le 45$

$-4/7 \le k \le 45/7 = 6.428\dots$

$k$ は整数なので、$0 \le k \le 6$。

したがって、$n=7k+5$ は $7(0)+5=5$ から $7(6)+5=47$ まで。

$4n+15=4(7k+5)+15=28k+35=7(4k+5)$

$3n+13=3(7k+5)+13=21k+28=7(3k+4)$

$4k+5$と$3k+4$が互いに素である必要がある。

$4k+5$ と $3k+4$ の最大公約数が1となるような $k$ を探す。

$k=0$のとき $n=5$, $4k+5=5$, $3k+4=4$, gcd(5,4)=1

$k=1$のとき $n=12$, $4k+5=9$, $3k+4=7$, gcd(9,7)=1

$k=2$のとき $n=19$, $4k+5=13$, $3k+4=10$, gcd(13,10)=1

$k=3$のとき $n=26$, $4k+5=17$, $3k+4=13$, gcd(17,13)=1

$k=4$のとき $n=33$, $4k+5=21$, $3k+4=16$, gcd(21,16)=1

$k=5$のとき $n=40$, $4k+5=25$, $3k+4=19$, gcd(25,19)=1

$k=6$のとき $n=47$, $4k+5=29$, $3k+4=22$, gcd(29,22)=1

$n=5, 12, 19, 26, 33, 40, 47$

(3)

$6n+9$ と $5n+8$ が互いに素となるような、100以下の自然数 $n$ の個数を求める。

$6n+9 = 3(2n+3)$

$6n+9$ と $5n+8$ が互いに素でないとき、3の倍数でないとすると、

$5n+8$ が3の倍数でないとき、

$5n+8 \equiv 0 \pmod{3}$

$2n+2 \equiv 0 \pmod{3}$

$2n \equiv -2 \equiv 1 \pmod{3}$

$4n \equiv 2 \pmod{3}$

$n \equiv 2 \pmod{3}$

$n=3k+2$

$6n+9$と$5n+8$が互いに素でないことは、GCD(6n+9, 5n+8)>1であることと同値である。

$GCD(6n+9, 5n+8)=GCD(5(6n+9)-6(5n+8),5n+8) = GCD(45-48,5n+8)=GCD(3, 5n+8)$.

この値が1よりも大きいためには、$5n+8$が3の倍数でなければならない。

$5n+8\equiv 0 \pmod{3}$

$5n\equiv -8 \pmod{3}$

$5n\equiv 1 \pmod{3}$

$10n \equiv 2 \pmod{3}$

$n\equiv 2 \pmod{3}$

つまり、nが3で割って2余る数であれば、$6n+9$と$5n+8$は互いに素ではない。

nは1から100までの自然数であるため、$n\equiv 2\pmod{3}$となるnの個数は、$\lfloor\frac{100-2}{3}\rfloor + 1 = \lfloor\frac{98}{3}\rfloor + 1 = 32+1 = 33$個

nが3で割って2余る数ではない数は、$100 - 33 = 67$個

3. 最終的な答え

(1) $n = 17, 27, 37, 47, 57, 67, 77, 87, 97$

(2) $n = 5, 12, 19, 26, 33, 40, 47$

(3) 67個