본문바로가기
주니어폴리매스 문제
문제를 찾고 일반화하세요!
[주니어폴리매스 문제] 코딩으로 '소수' 정복하기
수학동아 2019.10.05

코딩 수학 10번째 시간입니다. 다들 코딩을 이용해 수학 문제를 효율적으로 풀고 계신가요? 간단한 수학 문제는 손으로도 풀고 코딩으로도 풀 수 있지만, 실생활 문제나 어렵고 복잡한 함수가 포함된 수학 문제는 손으로 풀기 어려운 경우가 많아요. 코딩을 활용하면 쉽게 해결할 수 있으니 열심히 익히고 활용해 보세요~. 

코딩 명령어를 익힌 뒤에는 해당 코딩 명령어로 풀 수 있는 수학 문제를 찾아 댓글로 달고 친구들과 토론해 보세요!

 

 

 

 

세상의 비밀을 밝히는 열쇠 ‘소수'

 

 

이번에 코딩으로 정복해 볼 수학 개념은 ‘소수’예요. 소수는 1보다 큰 자연수 중 2, 3, 5, 7…처럼 1과 자기 자신으로만 나눠떨어지는 수로, 모든 자연수는 소수 아니면 소수의 곱으로 이뤄졌기 때문에 ‘수의 원소’라고 불리지요.

 

소수 연구는 고대 그리스 시대 유클리드, 에라토스테네스 같은 수학자가 소수의 개수와 소수를 찾는 방법 등을 연구한 이후 별다른 진전이 없었는데요, 페르마의 마지막 정리로 잘 알려진 17세기 프랑스의 아마추어 수학자 피에르 드 페르마에 의해 다시 활발히 연구되기 시작했어요. 놀라운 사실은 변호사였던 페르마가 일을 마치고 틈틈이 수학을 연구했는데 정수론, 확률론 분야에서 뛰어난 업적을 남겼다는 거예요. 

 

 

 소수의 성질을 체계적으로 연구한 프랑스 수학자 피에르 드 페르마(1607~1665).

 

 

페르마가 밝힌  소수의 성질 중 가장 잘 알려진 페르마의 소정리는 다음과 같습니다.

 

 

 

 

언뜻 보면 별거 아닌 것처럼 보이죠? 그런데 페르마의 소정리는 수학뿐 아니라 실생활에서도 아주 중요합니다. 현재 컴퓨터, 신용카드 등에 쓰이는 RSA 공개키 암호방식이 비밀번호를 암호화할 때 바로 페르마의 소정리가 쓰이기 때문이죠.

 

현재도 많은 수학자가 소수의 성질에 대해 활발히 연구하고 있습니다. 소수와 관련 있는 미해결 난제도 많은데요, 특히 100만 달러 상금이 걸린 밀레니엄 문제 하나인 리만 가설은 1부터 N 사이에 소수가 얼마나 많이 분포하고 있는지와 밀접하게 관련있는 문제인데, 최근 수학자 휴 몽고메리와 물리학자 프리먼 다이슨이 리만 가설과 양자역학에 등장하는 관계식이 비슷하다는 사실을 밝히면서 중요성이 더욱 부각되고 있죠. 

 

이번 호에서는 코딩 명령어를 이용해 소수를 찾아보고 소수와 관련 있는 다양한 수를 다루어보도록해요!

 

 

 

 

.

.

.

.

.

 

 

 

소수

list(primes), factor, gcd, lcm

 

 

소수를 찾는 코딩 명령어는 다음과 같다. 명령어의 구조를 이해한 뒤 폴리매스 홈페이지 [폴리매스]-[주니어폴리매스 문제]-[코딩 수학] 게시물에 있는 Sage 코딩창에 명령어를 입력해 소인수분해를 해보고 최대공약수와 최소공배수도 구해보자.

 

 

 

<1> 명령어 살펴보기

 

a부터 b까지 자연수 중에 1을 지운 뒤 2의 배수를 전부 지우고, 남은 수 중 3의 배수, 4의 배수…를 지우면 소수만 남는다. list(primes()) 명령어 괄호 안에 처음 자연수와 마지막 자연수를 쉼표로 구분해 입력하면 두 자연수 사이에 있는 소수를 모두 보여준다.

 

 

list(primes(a, b)

 

 

❷ ‘소인수분해’는 합성수를 두 소수의 곱으로 나타내는 것이다. factor() 명령어의 괄호안에 자연수를 입력하면 소인수분해한 결과를 보여준다.

 

 

N = an1 x bn2 x cn3 x ...

 

factor(N)

 

 

❸ 두 자연수를 소인수분해 했을 때 공통인 소인수를  최대공약수, 공통인 소인수와 공통인 아닌 나머지 수들의 곱이 최소공배수다. 각각 gcd(), lcm() 명령어의 괄호 안에 두 자연수를 쉼표로 구분해 입력하면 된다.

 

 

A = a x b x m,    B = a x b x n

최대공약수: a x b,  최소공배수: a x b x mn

 

gcd(A, B), lcm(A, B)

 

 

 

<2> Sage에서 명령어 실행하기

 

 

 

 

 

 

 

 

<3> 교과 연계 코너

 

미국에는 애벌레로 지내는 기간, 즉 생활 주기가 17년인 매미가 있다. 매미를 잡아먹는 천적의 생활 주기가 4년이면 매미와 천적의 생활 주기는 몇 년마다 겹칠까? 4와 17의 최소공배수인 68년마다 겹치므로 천적에게 잡아먹힐 위험이 덜하다. 

 

 

 

 

 

 

-----------------------

 

★도전 문제☆

 

① 매미의 생활 주기가 소수면 어떤 장점이 있는지 생각해보자.

 

 

 

RSA 공개키 암호 방식에 대한 알고리즘을 앞에서 배운 코딩 명령어로 구현해보자.

 

소수와 관련된 명령어로 해결할 수 있는 문제를 찾아 폴리매스 홈페이지에 올리고 친구들과 토론해보자.

 

 

 

-끝-

 

 

 

 

  •  
    김우현 기자 Lv.4 2019.10.05

    코딩창에서 gcd, lcm 명령어를 실행하면 오류가 발생하네요. 현재 확인 중에 있습니다!

     

     

    댓글 작성하기 좋아요0 댓글수1
  •  
    이용현 Lv.1 2019.10.07

    소수의 중요성을 다시금 깨닫게 해주는 내용이어서 좋았습니다.

    문제에 RSA 알고리즘은 이 주소에서 잘 나와있는 것 같습니다.

    https://djangoworld.tistory.com/16 참고하시면 좋을 것 같습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    je Lv.1 2019.10.15

    평소 궁금했던 소수에 대한 내용이라 더 재밌게 봤습니다ㅎㅎ

    댓글 작성하기 좋아요0 댓글수0
  •  
    21세기오일러 Lv.6 2019.10.16

    ㅠㅠ 저는 소수를 찾는 프로그램밖에 만들지 못했어요.

    파이썬으로 다른 거는 어떻게 하나요?

    댓글 작성하기 좋아요0 댓글수2
    •  
      휠릭시스 Lv.7 2019.10.22

      최대공약수는 일단 모든 수로 한 번씩 나눠보며 나눠지면 배열에 넣어놓는 것을 반복하여 나중에 모두 곱하고

      최소공배수는 두 수를 곱한 뒤 최대공약수로 나누세요

      좋아요0
    •  
      21세기오일러 Lv.6 2019.10.22

      감사합니다. 최소공배수를 그렇게하면 되는군요.

      좋아요0