소수 넷이 연달아 나오면 다섯째도 소수일 것이라는 생각이 듭니다. p = 2, 3, 5, 7은 3, 7, 31, 127을 줍니다 — 모두 소수이고, p가 소수일 때마다 2ᵖ − 1이 소수라고 믿고 싶어집니다. 틀렸습니다. 계산기는 2¹¹ − 1을 2047로 계산하고 23 × 89도 같은 2047입니다. 십일이 실패하는 첫 소수 지수이므로 메르센 소수는 공식이 아니라 탐색입니다.
실패는 우연이 아니고, 바로 그것이 검증 가능하게 만듭니다. 홀수 소수 p에서 소수 q가 2ᵖ − 1을 나누면 법 q에 대한 2의 위수는 p이고, 따라서 p가 q − 1을 나눕니다. q가 홀수이므로 2p도 q − 1을 나눕니다. 그러므로 2047의 모든 인수는 법 22에 대해 1과 합동이어야 하고, 23과 89는 곱해서 다시 그리로 이끄는 바로 그 둘입니다. 이런 좁히기가 메르센 수를 공격할 수 있게 하는 이유입니다. 어떤 산술이 시작되기도 전에 후보 거의 전부를 걸러냅니다.
답
2047
읽는 방법
계산기의 2¹¹ − 1이며 23 × 89도 같은 정수를 줍니다. 둘 다 정확합니다. 2047은 화면이 한 칸씩 세기를 멈추는 지점 2⁵³보다 한참 아래에 있습니다.
출처
Mersenne numbers 2ᵖ − 1, named after Marin Mersenne, whose list in Cogitata Physico-Mathematica (1644) was later proved wrong: 2⁶⁷ − 1 is composite, as Édouard Lucas showed in 1876
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.