在 1～100 之间的正整数 n 中，使得 n^2+7 与 n+4 不互质的 n 有几个？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

1-100 之間的正整數n 中，使得 n^2+7 與 n+4 不互質的 n 有幾個?

解:

n^2+7>n+4, n是自然數且n^2+7 與 n+4 不互質，則 n^2+7/n+4

n^2+7/(n+4)=(n+4)^2-8n-9 / (n+4)

= (n+4)^2-8(n+4)+23/(n+4)=(n+4)-8+23/(n+4)

n+4 必須是 23 的倍數  則 n^2+7 與 n+4 不互質的 ? (這句話為什麼?)

P/Q=(整數+a/b) ;  b 是a的倍數，則 P,Q 不互質? 為什麼?

luyuanhong

zhangzhong

按题意,依据余数定理知n 2+7与n+4的(最大)公约数应大于1, 即: (n 2+7, n+4)>1
依据余数定理知: (n 2+7, n+4)=( (n+4) 2－8(n+4)+23 , (n+4) )=(23, n+4)>1, 故n+4必须与23有大于1的公约数, 因23是素数, 故知n+4必须是23的倍数, 故知在1-100间使n 2+7与n+4不互质(素) 的n有且仅有4个:19,42,65,88.