본문 바로가기
반응형

오일러의 수3

프로젝트 오일러 #69 최대 오일러의 수 비율 이번 문제는 난이도 10%의 문제입니다. 사실 알고보면 어려운 문제는 아니지만, 오일러의 수라는 것에 대한 이해도가 없다면, 막막하게 느낄 수 있습니다. 오일러의 수는 어떤 수 n에 대하여, n보다 작을 자연수 중에, n과 서로소인 수의 갯수를 말합니다. 이 수는 암호학 등에서 아주 중요하게 다루어집니다. RSA와 같이 비대칭 키를 사용하는 암호학을 공부하고자 한다면, 오일러의 수를 이해하지 못 하면, 절대 해당 암호학을 이해할 수 없습니다. 대학에서 정수론이라는 과목을 들었다면 모를까, 그렇지 않다면, 배울 수 있는 기회는 별로 없죠. (요즘은 중학생들도 이것을 아는 애들이 있습니다. 수학 올림피아드에서 가끔씩 나오는 문제이다보니. 제 경우에는 정수론 책을 하나 사서 독학을 했습니다.) 문제에서는 n에.. 2016. 9. 27.
26. 프로젝트 오일러 #26 : 순환고리 이번 문제는 가장 긴 순환고리를 찾는 문제입니다. 사실 순환고리는 오일러의 수 문제로 귀결됩니다. 오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다. 라고 한다면, 오일러의 수는 이라고 할 수 있습니다. 즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다. n이 소수라면 n-1 이 오일러의 수가 됩니다. 가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다. 10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 하나의 순환고리를 갖습니다. 일단 2의 배수와 5의 배수는 비순환고리를 가짐으로 실제 검사할 숫자들은입니다. 이 숫자 이외에는 비순환고리를 만듭니다. 예를 들어서 6.. 2015. 2. 27.
\(\varphi(x)+\varphi(y)+\varphi(z)\)의 최소값 문제 문제 출처는 중학 수학 문제지입니다. 사실 그 때, 문제 풀었을 때, 문제지 답지가 틀렸었던 문제였습니다. 문제 출제하신 분이 좀 착각을 했었던 듯 합니다. 사실 중학 수학 문제에 정수론에서 사용되는 것들을 사용하는 것은 바람직하지 않습니다. 정수론과 관련해서 용어를 설명드리겠습니다. 서로 소는 두개의 수에 대한 소인수 분해하여 공통 인자가 없는 경우입니다. 즉, 최대 공약수가 1이라는 뜻입니다. \(\varphi(x)\)는 x보다 작은 자연수 중에서 x와 서로 소인 수의 개수를 뜻하며, 오일러의 수(Euler's totient)라고 합니다. \( (a, b) = g \) 형태의 표현법은 a와 b 수의 최대 공약수가 g라는 표현입니다. \( \sigma (x) \) 는 x의 약수의 합을 말합니다. 문제).. 2011. 9. 30.
728x90