이 폴더에 있는 모든 글 목록입니다:
배수판정법: 익숙한 끝자리에서 낯선 17의 배수까지 《나머지에서 시작하는 정수론》 · 1/8편 · 배수 판정법 0. 서론: 기억을 복원하면서 시작해봅시다 2의 배수는 짝수, 5의 배수는 끝자리가 0이나 5. 여기까지는 오래전에 배운 기억이 금방 돌아올 겁니다. 3과 9는 각 자리 숫자를 더했던 것 같습니다. 4와 8은… 솔직히 잘 기억이 안날 수도 있습니다. 어렴풋이 기억에서 끌어내 보자면 끝 두 자리, 끝 세 자리를 보았던 것 같고요. 그런데 7의 배수인지 묻는 순간 손이 멈춥니다. ...
배수 판정법의 원리: 20과 21의 차이 하나가 만드는 규칙 《나머지에서 시작하는 정수론》 · 2/8편 · 배수 판정법의 원리 0. 서론: 잘 쓰이는 규칙을 직접 만들 수 있을까요 앞 편에서 203을 7의 규칙으로 바꾸면 $20-2\times3=14$가 되었습니다. 286을 13의 규칙으로 바꾸면 $28+4\times6=52$가 되었습니다. 둘 다 작은 수를 보고 큰 수의 배수 여부를 판단했습니다. 그런데 숫자를 바꾸었는데도 어떻게 같은 답을 얻을까요? 이번 편에서 다룰 정보는 나머지입니다. 나누는 수를 정하고 나면, 어떤 수들은 크기가 달라도 같은 나머지를 가집니다. 이 관계를 이용하면 큰 자릿값을 1이나 $-1$처럼 간단한 값으로 바꿀 수 있습니다. 7·13·17·19의 서로 다른 계수도 같은 원리에서 얻습니다. ...
최대공약수의 비밀: 나눗셈의 끝에서 시작되는 역주행 《나머지에서 시작하는 정수론》 · 3/8편 · 최대공약수의 비밀 0. 서론: 학교에서 배운 최대공약수부터 최대공약수라고 하면 어떤 계산이 먼저 떠오르시나요? 두 수를 나란히 적고, 공통으로 나누어떨어지는 수를 왼쪽에 쓰며 아래로 내려가던 풀이가 익숙할 겁니다. 왼쪽에 적은 수만 직선으로 곱하면 최대공약수, 마지막 줄의 두 수까지 ㄴ자로 곱하면 최소공배수가 되던 그 계산입니다. 이번 편은 그 풀이에서 출발하겠습니다. 그리고 교육과정에서도 바로 뒤에 나오는 소인수분해로 같은 답을 얻는 이유를 짚은 뒤, 두 수의 소인수를 모두 찾지 않고 최대공약수를 구하는 유클리드 호제법으로 넘어가겠습니다. ...
페르마의 소정리: 나머지를 모두 곱하면 거듭제곱이 보입니다 《나머지에서 시작하는 정수론》 · 4/8편 · 페르마의 소정리 0. 서론: 큰 거듭제곱을 작은 계산으로 바꾸려면 $3^{100}$은 손으로 계산하기에도 큰 정수입니다. 하지만 만약 11로 나눈 나머지만 필요하다면 그 정수 전체를 만들 이유가 없습니다. 지금까지 따라오셨다면, 느낌이 오시죠? 배수판정법에서 사용했던 원리를 이번에는 거듭제곱에 적용하는 것입니다. 만약 $3^{10}$을 11로 나눈 나머지가 1이라는 사실을 알고 있다면 어떻게 될까요? 3을 백 번 곱하는 대신, 열 번씩 곱한 덩어리를 열 개 만들면 됩니다. ...
오일러의 정리: 남길 수를 직접 세면 지수가 정해집니다 《나머지에서 시작하는 정수론》 · 5/8편 · 오일러의 정리 0. 서론: 합성수에서는 어느 나머지를 남길까요 페르마의 소정리에서는 소수 $p$로 나눈 0이 아닌 나머지 전체를 목록으로 사용했습니다. 각각에 $p$의 배수가 아닌 수를 곱하면 목록이 재배열되었고, 전체 곱을 비교하여 $a^{p-1}\equiv1\pmod p$를 얻었습니다. 법이 12라면 어떻게 될까요? 0이 아니라고 모두 역원을 갖는 것은 아닙니다. 2는 12와 공통인수 2를 갖고, 3은 공통인수 3을 가집니다. 반면 1·5·7·11은 12와 서로소여서 역원이 있습니다. ...