대한수학회 58번
방정식의 정수 해는 몇 개일까?
문제 출제자 : 오병권 서울대학교 수리과학부 교수
정수 전체의 집합을 라 하고, 소수 전체의 집합을
라 정의하자. 또한, 집합
에 대하여
는
의 원소의 개수를 말한다. 정수 계수의 이변수 다항식
와 정수
에 대하여
,
라 정의하자. 예를 들어,
이다.
(i) 임의의 소수 에 대하여,
은 3의 배수이다 ⇐⇒
이
의 배수인 정수
가 존재한다
임을 이용하여 을 구하여라.
(ii) 임의의 소수 와 양의 정수
에 대하여
을 구하여라. 이를 이용하여 을 구하여라.
이제
이라 정의하자.
(iii) 임의의 소수 와 양의 정수
에 대하여,
을 구하여라.
(iv) 임의의 소수 와 양의 정수 a에 대하여,
을 구하여라.
(v) 임의의 소수 와 양의 정수 a, b에 대하여,
을 구하여라.
===================================================================================================
대한수학회 58번 문제가 너무 어렵나요? 그렇다면 문제를 출제해주신 오병권 교수님의 문제 풀이 일부분을 참고해보세요! 교수님께서 특별히 제공해주셨습니다.
<오병권 교수님의 58번 문제 풀이 일부>
이
의 배수라고 하자. 당연히
이다. 또한, 주어진 힌트에 의하여
이
의 배수인 정수
가 존재한다. 따라서 방정식
가 정수해
를 갖는 양의 정수
가 존재한다. 그러한 양의 정수
가운데 가장 작은 양의 정수를
이라 하자. 즉, 방정식
를 만족하는 정수 가 존재하지만,
인 양의 정수
에 대해서는
는 정수 해가 존재하지 않는다고 가정하자. 이제
임을 보이자. 우선
인 정수 에 대해서도
은
의 배수이고
이므로
라 가정할 수 있다.
라 가정하자. 정수
를
을 만족하도록 잡자. 만약 를 만족하는 짝수이고
라면
를 만족하므로
이고
는 짝수이며
이므로 증명이 끝난다. 따라서
또는
가운데 하나는
보다 크다고 가정할 수 있다. 또한
이면
는
의 배수가 되고
또는
가 되어 모순이다. 한편,
이므로 를 만족하는 양의 정수
가 존재한다. 또한
이 성립하고
을 만족하므로
가 성립한다. 즉, 방정식 도 역시 정수해가 존재한다. 마지막으로
이므로 이고, 이는 가정에 모순이다. 따라서 최소의 정수
은
이다. 즉,
는 정수 해가 존재한다.
끝.
쉽게 말해서
R은 정수해의 집합을 말하는 것이고 r은 정수해의 개수를 말하는 거라고 보시면 됩니다
5번문제의 "" 에서 p^a,q^b가 정확히 어떤 것을 의미하는지 모르겠습니다. (p^a)x(q^b) 을 의미하는 것 인가요?
1번 문제부터 해결하기 위해서는 먼저 p-1이 3k+1꼴일때의 해가 없다는 것을 증명하고 p-1이 3의 배수일때는 x2+3y2=a2+3b2=소수 p를 동시에 만족하는 a와 b가 없다는 것을 증명해야 할 것입니다! 이 문제에 무한 강하법이나 이차잉여를 쓰는 것이 어떨까요? 아니면 브라마굽타-피보나치 항등식을 쓰는 것도 좋을 것 같네요.
우선 p-1이 3k+1 꼴일 때는 쉽네요. 이때 p의 mod 3 값은 2입니다.
p = x^2 + 3y^2이어야 하므로 x^2 + 3y^2의 mod 3 값도 2일테고, 3y^2은 3의 배수이므로 이는 곧 x^2의 mod 3값이 2라는 뜻입니다.
그런데 임의의 제곱수의 mod 3 값은 0,1이므로 이를 만족하는 x는 존재하지 않습니다.
따라서 p-1이 3k+1 꼴일 때는 해가 존재하지 않습니다. p-1이 3k 꼴일 때는 더 고민해봐야겠어요.
(p.s p가 3k 꼴일 때를 빠뜨리신 듯 한데, 이때 p = 3이므로 (x, y) = (0, 1), (0, -1)로 답은 2개입니다.)
혹시 p-1이 3의 배수일떄 어떤 방법을 쓸지 한번 고민해보셨나요?? 갈피를 못잡겠어요...
이 문제는 '페르마의 두 제곱수 정리'와 상당히 연관이 있습니다. 그 정리를 책과 인터넷으로 찾아보았고 그것을 토대로 풀고 있습니다.
와 방금 전에 구글로 그거 찾아서 보고 있었는데... 이것은...문제를 반드시 푼다는...예언..?
https://terms.naver.com/entry.naver?docId=5669129&cid=60207&categoryId=60207 여기 참고해서 풀었습니다. 풀이는 페르마의 두 제곱수 정리 유일성 증명과 매우 유사하네요.
(1) p가 3k+1 꼴일 때 해가 1개 이상 존재한다는 것은 힌트를 통해 알 수 있다.
이제 부호를 무시하면 해가 1개만 존재한다는 것을 보이겠다.
p = a^2 + 3b^2 = c^2 + 3d^2(a,b,c,d > 0)라 하자. 이때 (a,b)와 (c,d)는 부호만 다른 것이 아닌 완전히 다른 해이다.
(p - a^2) * 3d^2 = 9(bd)^2 = (p - c^2) * 3b^2이 성립한다. 이를 정리하면 3p(d^2 - b^2) = 3((ad)^2 - (bc)^2)이 되고, 양변을 3으로 나누면 p(d^2 - b^2) = (ad+bc)(ad-bc)가 된다.
p | (좌변)이므로 p | (우변)이 성립하므로, p | ad+bc 혹은 p | ad-bc가 성립한다.
p | ad+bc이면 ad+bc가 양수이므로 ad+bc >= p이다. 그런데 p^2 = (a^2 + 3b^2)(c^2 + 3d^2) = 3(ad+bc)^2 + (ac-3bd)^2 >= 3p^2가 되므로 이는 불가능하다.
p | ad-bc이면 p^2 = (a^2 + 3b^2)(c^2 + 3d^2) = 3(ad-bc)^2 + (ac+3bd)^2이므로 |ad-bc| >= p이면 위와 같은 이유로 불가능하다. 따라서 ad-bc = 0이다.
이때 p(d^2 - b^2) = (ad+bc)(ad-bc) = 0이 되므로 d^2 - b^2 = 0이다. 따라서 d = b이며, a = c이다.
하지만 이는 (a,b)와 (c,d)가 완전히 다른 해라는 가정에 모순이므로 이 역시 불가능하다.
따라서 부호를 무시하면 해는 1개이다. 이때 부호를 고려하면 답은 4개이다.
흠.. 지금 맞는지 틀렸는지 모르겠어서 댓글 썼다가 지웠다가 하고 있는데 우선 두 번째 케이스에서 (x,y) = (p^n, 0)이라는 해는 틀린 것 같습니다. gcd(0, p) = p니까요.
그리고 두 증명 모두 해가 2개 이상 존재하지 않는다를 보인 것 같으며 최소한 1개가 존재한다는 아직 증명하지 못한 것 같습니다.
(p.s. 첫 번째 증명에서 무한강하법을 사용하였는데 gcd(xy, p) = 1이라는 문제 조건이 있으니까 그냥 a,b,c,d 중 적어도 하나가 p의 배수가 되니까 모순이다 이렇게 끝내도 될 것 같네요.)
아 이거 그 gcd그거 있잖아요 그거는 힌트일 뿐이고 gcd랑 문제는 다른 거에요! gcd랑 x,y의 조건은 다른거에요!
그리고 새벽에 써서 a,b,c,d는 결국 원래의 식과 같아지니(우변이 p인 경우로) 결국 해가 한개다. 라는 걸 깜빡했네요!!
흠... 그러면 gcd(xy, p)가 1이 아니어도 된다는 뜻인가요?
하지만 그러면 p = 7, a = 3일 때 (x,y) = (14, 7), (10, 9)로 해가 2개가 나오는데요.
아무래도 p = 3k+1일 때의 증명에서 p의 지수는 유한하므로 반복하다 보면 언젠간 p의 지수가 더 이상 반복할 수 없을테고, 이때 a,b,c의 지수도 더 이상 커지지 않으므로 무한강하를 쓰는 것이 불가능해 보입니다.
첫 번쨰 질문의 답은
a가 홀수일 때는 원래의 p일때의 해에 p의 짝수 지수를 곱하면 해가 나오니 이것을 별개로 해가 1개가 나오고,
나머지는 gcd(xy,p)=1일때의 근이 나오는 것이죠!
새벽에 써서 정리를 못하고 생각나는 것만 적다보니;; 지금 정리하고 있습니다!
그리고 두 번쨰 질문의 답은 무한강하라는 표현이 조금 이상했는데.......
계속 p로 나누면 원래의 x^2+3y^2=p 라는 식이 나오니 이것은 그전의 증명을 통해서 할 수 있습니다!
아하! 그런 거군요 제가 처음에 문제 이해를 약간 잘못해서 조금 헤멨는데 저도 본격적으로 풀어보겠습니다.
p가 3일땐 어떻게 할까요?
저는 감이 잘 안 와서 C언어로 50 이하의 모든 소수 p와 1~10 정도의 a로 모든 정수해를 구해보았습니다.
그 결과 p가 3k+2, 3일 때는 님이 구한 답이랑 일치하였습니다.(단, p = 2일 때는 a가 짝수면 부호 무시했을 때 2개, a가 홀수면 0개가 나왔습니다)
하지만 p가 3k+1일 때는 a가 짝수면 서로소인 해 1개, 서로소 아닌 해 a/2개가 나왔고 a가 홀수면 서로소인 해 1개, 서로소 아닌 해 (a-1)/2개가 나오네요.
아아 수정하겠습니다;;
p가 3k+1일때
서로소가 아닐때, 강하를 계속 하여서 원래의 식으로 만들었잖아요??
한번 강하를 할때는 한 개의 순수근(서로소 근)이 나오고, 두번 하면 두개가 나오고... 이렇게 해서 원래의 식이 될때까지 강하를 하면
그 강하를 한 때의 순수근은 a가 짝수일 때 a/2개가 나오고, 홀수면 (a-1)/2개가 나옵니다. 이것들까지 포함시켜서 개수를 세면 a가 짝수일 때 a/2개가 나오고, 홀수면 (a-1)/2개가 나오겠죠.
그래서, 총정리에서 답을 수정하면,
p가 3k+1일때,
서로소근은 1개가 나오고, 서로소가 아닌 근은 a가 짝수일 때 a/2개가 나오고, 홀수면 (a-1)/2개가 나옵니다. 이것을 +,-까지 포함해서 계산을 하면, 모든 정수근까지 나오겠지요.
그전의 개수는 0을 포함한 자연수 근의 개수입니다!
그리고...혹시... C언어 코드좀...아예 모르지만...한번 해보고 싶어서요...
#include <stdio.h>
#include <math.h>
int main()
{
int a[15] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int i, j;
unsigned long long number, y;
for (i = 0; i <= 14; i++) {
for (j = 1; j <= 13; j++) {
number = pow(a[i], j);
for (y = 0; y <= floor(sqrt(number / 3)); y++) {
if (sqrt(number - 3*y*y) == floor(sqrt(number - 3*y*y))) {
printf("p = %d and b = %d -> x = %f and y = %llu \n", a[i], j, sqrt(number - 3*y*y), y);
}
}
}
}
return 0;
}
이거입니다. 처음의 {2,3,5,..47} 이거가 50 이하의 소수 리스트이므로 소수를 추가하거나 빼고 싶으면 안에 더 넣거나 빼면 됩니다. j = 1; j <= 13; j++ 여기서 1~13이 a의 범위이므로 j의 범위를 수정할 수 있습니다. (예를 들어 2~10으로 하고 싶으면 j = 2; j <= 10; j++ 이렇게 하면 됩니다) 그런데 주의할 점이 있다면 거듭제곱 꼴은 수가 매우 커질 수 있기 때문에 j의 값이 너무 커지면 모든 해를 출력하지 못하거나 엉뚱한 수를 출력할 수 있습니다. (저도 C언어 그다지 잘하는 편은 아니라서..ㅎㅎ )13으로 해놓으면 p가 19, 11로 해놓으면 p가 37 쯤에서 이상해지네요.
감사합니다! 꼭 한번 해보겠습니다! 수학 코딩이라!
흠 근데 곰곰이 살펴보니 p = 3k+2일 때 p^2a = 3(ad+bc)^2 + (ac-3bd)^2 = 4(ad)^2 이 식 아무래도 틀린 것 같습니다.
b = 0이라고 했을 때 3(ad)^2 + (ac)^2 = 4(ad)^2 가 성립할 리가 없지 않나요?
답은 맞는 것 같긴 한데, 증명에 수정이 필요할 것 같습니다.
어 그러네요 알파벳 잘못 봤네요!
b가 0이면, p^a=a^2이 되니 a=p^(a/2)이 되니,
사진 속 밑의 식처럼 x=p^(a/2), y=0이 되서 증명이 됩니다!
제 증명 깊이 봐서 오류를 찾아주셔서 감사합니다!
세상살이 이렇게 같이 즐겁게 사는 거죠!(?)
어...그런건가요? 그런데 x,y는 위에서 이미 정의해놓았고, 저 식이 틀리면 해가 1개라는 증명이 무산되는 건 아닌가요?
2번은 상당히 헷갈리는 문제네요..저도 더 고민해보겠습니다.
아아 원래는 틀렸다고 했는데 이제 보니 해가 하나 나와요!
근데 원래는 식이 틀렸다고 했고, 이 모든 식과 별개로 하나의 해가 존재하니 이 해가 유일한 해다. 이렇게 했었거든요.
근데 이 기회로 완전한 식으로 해가 하나밖에 나오지 않는다. 이걸로 증명을 하니 증명이 더 탄탄해진 거죠!
글쎼요..하지만 그런 접근은 3(ad)^2 + (ac)^2 = 4(ad)^2 이 식이 참일 때만 성립하는데요.
애초에 이 식 자체가 알파벳 실수로 인해서 나온 잘못된 식이므로, 이 식 이후의 모든 증명은 수정이 필요하지 않을까요?
어떤 접근을...말하시는 거에요??
음 간단히 요약하자면 3(ad)^2 + (ac)^2 = 4(ad)^2이 식 자체가 알파벳을 잘못 봐서 나온 잘못된 식이므로 애초에 활용할 수 없는 잘못된 식이라는 뜻입니다.
그러니까..아마 수정이 필요할 것 같네요...고민해보겠습니다.
아 네 맞아요 그거 사용할 수 없어요! 근데, 기존의 식 p^a=a^2+3b^2에서 b에 0을 대입하여서 그전의 댓글이 된 것이에요! 그전의 식은 사용 안한거에요!
근데 그러면 b가 1 이상일 때의 정수해가 없다는 보장이 없지 않나요?(으아 진짜 헷갈리네요)
아 이거 우선 확실한 해 하나 잡아놓고 해가 하나 더 있으면 안된다! 라는 그 식을 써서 아예 나머지 해가 없도록 증명을 한 것이에요!
님
진짜진짜 죄송한데
혹시 3k+2일 때 풀이를 말로 풀어서 써주실 수 있을까요? 진짜 죄송한 부탁이지만 이해가 잘 안 되서요... 부탁합니다.
일단은 주요만 설명드릴게요.
우선, 확실한 해는 x=p^(a/2), y=0이다.
이 친구들을 a,b라 하고, 나머지 다른 한 근이 있다면, c,d라 하자.
p=3k+1때 썼던 방법으로 하면(이건 쓸 게 너무 많아서...) c,d는 존재하지 않는다.
그래서, a,b 근 한개만 있는 것이다.
pure math님과 진리를 찾아서님의 문제 푸는 모습 너무 멋져요~!
현재 폴리매스 어셈블 멘토분들에게 문제 풀이 확인 요청을 드렸어요~ 3일 이내에 답변 주실거예요!
조금 기다려주세요~
감사합니다!
풀이과정에 변수가 겹치는 등의 오류가 있습니다.
또한 3k+1꼴 소수의 경우 해 counting이 잘못되었습니다. (xy,p)가 1이 아닌 경우를 다시 생각해보세요.
아 저기 위에 댓글에 있습니다! 저기서 진리를 찾아서님과 함께 카운팅 수정 했습니다! 원하신다면 정리해서 드리겠습니다!
부분해결... 정말 감사합니다...
넵 카운팅 확인했습니다.
여담으로, 서술 과정에서 동치 기호 등의 수학 기호의 사용을 조금 더 신경 쓰는 것이 좋을 듯 합니다.
또한 "계속 반복하면", "그래서" 등의 구어체보다는 그 반복 구간을 a라 지칭하고 a를 반복한다거나, "따라서" 같은 표현을 쓰는 것이 조금 더 명확할 것 같습니다.
아아;; 문법 확인하겠습니다! 명확해져야 되겠군요... 존경하고, 싸랑합니다! 헤헤
3번 문제에 관하여
3번 문제의 개수(S집합 관여 X)는 2번 문제에서 y가 3의 배수일때의 개수만 구하면 되죠. 그러면 제가 2번 문제를 푼 총정리에서(밑의 댓글 참고해서 약간의 수정이 있었음, 수정은 댓글에 있음) 3의 배수인 것들이 다 나와요! 그것들을 정리하고, 특정 경우에 한해 3의 배수를 증명, 그 후에 S집합 정의 후 증명하면 될 것 같아요!
P=3일때는 (3번 문제)
x^2+27y^2=3^a, x=3x'이라 하면 x'^2+3y^2=3^(a-1)이 됩니다.
그리고 뒤의 저의 2번 문제의 답에서
이 식의 해가 a=짝수일때 x'=3^(a/2), y=0이 나오고
a=홀수일때 x'은 0, y=3^(a-1)/2가 나옵니다. 여기에 x'에 3을 곱해주면
a=짝수, x=3^(a/2+1), y=0이 나오고
a=홀수, x=0, y=3^(a-1)/2가 나옵니다.