첫댓글 gcd(n^2+7,n+4) = gcd(n^2+7-n*(n+4),n+4) = gcd(-4n+7,n+4) = gcd(-4n+7+4*(n+4),n+4) = gcd(23,n+4) 따라서 n=23k-4의 꼴이면 n^2+7과 n+4는 1이 아닌 공약수(사실상 23)를 갖습니다. 위에서 사용한 식은 유클리드의 호제법입니다.
호제법은 간단히 말해서 gcd(a,b) = gcd(a-b,b)입니다. 따라서 gcd(a,b)=gcd(a-cb,b)도 성립하지요.
첫댓글 gcd(n^2+7,n+4) = gcd(n^2+7-n*(n+4),n+4) = gcd(-4n+7,n+4) = gcd(-4n+7+4*(n+4),n+4) = gcd(23,n+4) 따라서 n=23k-4의 꼴이면 n^2+7과 n+4는 1이 아닌 공약수(사실상 23)를 갖습니다. 위에서 사용한 식은 유클리드의 호제법입니다.
호제법은 간단히 말해서 gcd(a,b) = gcd(a-b,b)입니다. 따라서 gcd(a,b)=gcd(a-cb,b)도 성립하지요.