간단한 숫자. 숫자가 소수인지 확인하는 방법

제수 목록.정의에 따르면 숫자 N 2와 1과 자신 이외의 정수로 균등하게 나눌 수 없는 경우에만 소수입니다. 위의 공식은 불필요한 단계를 제거하고 시간을 절약합니다. 예를 들어 숫자가 3의 배수인지 확인한 후 9의 배수인지 확인할 필요가 없습니다.

• floor(x) 함수는 x를 x보다 작거나 같은 가장 가까운 정수로 반올림합니다.

모듈식 산술에 대해 알아봅니다."x mod y" 연산(mod는 "모듈"을 의미하는 라틴어 "modulo"의 줄임말)은 "x를 y로 나누고 나머지를 구하라"는 의미입니다. 즉, 모듈식 산술에서 특정 값에 도달하면 이를 기준 치수, 숫자는 다시 0으로 "돌아갑니다". 예를 들어 시계는 모듈러스 12로 시간을 측정합니다. 시계는 10시, 11시, 12시를 표시한 다음 1로 돌아갑니다.

• 많은 계산기에는 모드 키가 있습니다. 이 섹션의 끝은 큰 숫자에 대해 이 함수를 수동으로 계산하는 방법을 보여줍니다.

• 번역

소수의 속성은 수학자에 의해 처음 연구되었습니다. 고대 그리스. 수학자 피타고라스 학파(500 - 300 BC) 소수의 신비하고 수비학적 속성에 주로 관심이 있었습니다. 그들은 완벽하고 친숙한 숫자에 대한 아이디어를 처음으로 생각해 냈습니다.

완전수는 자신과 같은 약수를 가집니다. 예를 들어, 숫자 6의 고유 제수는 1, 2 및 3입니다. 1 + 2 + 3 = 6입니다. 숫자 28의 제수는 1, 2, 4, 7 및 14입니다. 게다가 1 + 2 + 4 + 7 + 14 = 28.

한 숫자의 고유 약수의 합이 다른 숫자와 같거나 그 반대의 경우(예: 220 및 284) 숫자를 우호적이라고 합니다. 완전한 숫자는 그 자체에 우호적이라고 말할 수 있습니다.

기원전 300년에 유클리드의 "시작" 작품이 등장할 때까지. 여러 가지가 이미 입증되었습니다. 중요한 사실소수에 대해. 원소 제9권에서 유클리드는 소수가 무한히 존재함을 증명했습니다. 그건 그렇고, 이것은 모순에 의한 증명의 사용의 첫 번째 예 중 하나입니다. 그는 또한 산술의 기본 정리를 증명합니다. 모든 정수는 소수의 곱으로 고유한 방식으로 표현될 수 있습니다.

그는 또한 숫자 2 n -1이 소수이면 숫자 2 n-1 * (2 n -1)이 완전함을 보여주었습니다. 1747년 또 다른 수학자 오일러는 모든 짝수 짝수도 이 형식으로 쓸 수 있음을 보여줄 수 있었습니다. 오늘날까지 홀수 완전수가 존재하는지 여부는 알려져 있지 않습니다.

기원전 200년 그리스의 에라토스테네스는 에라토스테네스의 체(Sieve of Eratosthenes)라는 소수를 찾는 알고리즘을 고안했습니다.

그리고 중세와 관련된 소수 연구의 역사에서 큰 단절이 있었습니다.

다음과 같은 발견은 수학자 페르마에 의해 17세기 초에 이미 이루어졌습니다. 그는 4n+1 형식의 모든 소수를 쓸 수 있다는 Albert Girard의 추측을 증명했습니다. 독특한 방식으로두 제곱의 합으로 계산하고 어떤 수도 네 제곱의 합으로 나타낼 수 있다는 정리를 공식화했습니다.

그는 개발 새로운 방법큰 수를 인수분해하고 숫자 2027651281 = 44021 × 46061에서 증명했습니다. 그는 또한 페르마의 작은 정리를 증명했습니다. p가 소수이면 a p = a 모듈로 p는 모든 정수 a에 대해 참입니다.

이 진술은 "중국 가설"로 알려진 것의 절반을 증명하며 2000년 전으로 거슬러 올라갑니다. 정수 n은 2n-2가 n으로 나눌 수 있는 경우에만 소수입니다. 가설의 두 번째 부분은 거짓으로 판명되었습니다. 예를 들어 2341 - 2는 341로 나눌 수 있지만 숫자 341은 341 = 31 × 11입니다.

페르마의 작은 정리는 숫자 이론의 다른 많은 결과와 숫자가 소수인지 테스트하는 방법의 기초가 되었으며, 그 중 많은 것들이 오늘날에도 여전히 사용되고 있습니다.

페르마는 동시대 사람들, 특히 마린 메르센느라는 수도사와 광범위하게 서신을 교환했습니다. 그의 편지 중 하나에서 그는 n이 2의 거듭제곱이면 2 n + 1 형식의 숫자가 항상 소수일 것이라고 추측했습니다. 그는 이것을 n = 1, 2, 4, 8, 16에 대해 테스트했으며 n이 2의 거듭제곱이 아닐 때 숫자가 반드시 소수는 아니라는 것을 확신했습니다. 이 숫자를 페르마 수라고 하며 100년 후 오일러가 다음 숫자인 232 + 1 = 4294967297이 641로 나누어 떨어지므로 소수가 아님을 보여주었습니다.

2 n - 1 형식의 숫자도 연구 대상이었습니다. n이 합성이면 숫자 자체도 합성이라는 것을 쉽게 보여주기 때문입니다. 이 수를 그가 적극적으로 연구했기 때문에 메르센 수라고 합니다.

그러나 n이 소수인 2 n - 1 형식의 모든 숫자가 소수인 것은 아닙니다. 예를 들어, 2 11 - 1 = 2047 = 23 * 89입니다. 이것은 1536년에 처음 발견되었습니다.

수년 동안 이러한 종류의 수는 수학자에게 알려진 가장 큰 소수를 제공했습니다. M 19는 1588년 카탈디에 의해 증명되었으며 오일러가 M 31도 소수임을 증명할 때까지 200년 동안 알려진 가장 큰 소수였습니다. 이 기록은 또 100년 동안 유지되었고 Lucas는 M 127이 소수임을 보여주었고(이것은 이미 39자리 숫자임), 그 후 컴퓨터의 출현으로 연구가 계속되었습니다.

1952년에 M 521 , M 607 , M 1279 , M 2203 및 M 2281 숫자의 소수가 증명되었습니다.

2005년까지 42개의 메르센 소수가 발견되었습니다. 그 중 가장 큰 M 25964951 은 7816230자리로 구성되어 있습니다.

오일러의 작업은 소수를 포함한 정수론에 큰 영향을 미쳤습니다. 그는 페르마의 작은 정리를 확장하고 φ-함수를 도입했습니다. 5번째 페르마 수 2 32 +1을 인수분해하고, 60쌍의 우호적인 수를 찾고, 상호성의 2차 법칙을 공식화했습니다(그러나 증명하지 못했습니다).

그는 수학적 분석 방법을 처음으로 소개하고 숫자의 분석 이론을 개발했습니다. 그는 고조파 급수 ∑ (1/n)뿐만 아니라 형식의 급수도 증명했습니다.

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

소수에 역수인 양의 합으로 구해지며 발산합니다. 고조파 급수의 n항의 합은 대략 log(n)처럼 증가하는 반면, 두 번째 급수는 log[ log(n) ]처럼 더 천천히 발산합니다. 이것은 예를 들어 시리즈가 여전히 발산하더라도 현재까지 발견된 모든 소수의 역수의 합은 4를 제공한다는 것을 의미합니다.

언뜻보기에 소수는 정수 사이에 다소 무작위로 분포되어 있는 것처럼 보입니다. 예를 들어 10000000 바로 앞의 100개의 숫자 중 9개의 소수가 있고 이 값 바로 뒤의 100개의 숫자 중 2개의 숫자만 있습니다. 그러나 큰 세그먼트에서는 소수가 상당히 고르게 분포됩니다. Legendre와 Gauss는 그들의 분포를 다루었습니다. Gauss는 한 번 친구에게 무료 15분 동안 그는 항상 다음 1000개의 숫자에 있는 소수의 수를 센다고 말했습니다. 말년에 그는 300만까지의 모든 소수를 세었습니다. Legendre와 Gauss는 큰 n에 대해 소수의 밀도가 1/log(n)이라고 동등하게 계산했습니다. Legendre는 1과 n 사이의 소수의 수를 다음과 같이 추정했습니다.

π(n) = n/(log(n) - 1.08366)

그리고 가우스 - 대수 적분

π(n) = / 1/log(t) dt

2에서 n까지의 적분 간격으로.

소수 1/log(n)의 밀도에 대한 설명은 소수 정리로 알려져 있습니다. 그들은 19세기 내내 그것을 증명하려고 노력했고 Chebyshev와 Riemann은 진전을 이루었습니다. 그들은 그것을 리만 제타 함수의 0 분포에 대한 지금까지 입증되지 않은 추측인 리만 가설과 연결했습니다. 소수의 밀도는 1896년 Hadamard와 de la Vallée-Poussin에 의해 동시에 증명되었습니다.

소수 이론에는 아직 해결되지 않은 질문이 많이 있으며 그 중 일부는 수백 년이 넘었습니다.

• 쌍둥이 소수 가설 - 서로 2만큼 다른 소수 쌍의 무한 수에 대한
• Goldbach의 추측: 4부터 시작하는 모든 짝수는 두 소수의 합으로 나타낼 수 있습니다.
• n 2 + 1 형태의 소수가 무한히 존재합니까?
• n 2 와 (n + 1) 2 사이의 소수를 찾는 것이 항상 가능합니까? (n과 2n 사이에 항상 소수가 있다는 사실은 Chebyshev에 의해 증명되었습니다)
• 페르마 소수는 무한히 존재합니까? 4일 이후에 페르마 소수가 있습니까?
• 주어진 길이에 대해 연속적인 소수의 산술적 진행이 있습니까? 예를 들어, 길이 4의 경우: 251, 257, 263, 269 발견된 최대 길이는 26 입니다.
• 산술 수열에서 연속되는 세 개의 소수 집합의 수는 무한합니까?
• n 2 - n + 41은 0 ≤ n ≤ 40에 대한 소수입니다. 그러한 소수가 무한히 있습니까? 공식 n 2 - 79 n + 1601에 대한 동일한 질문입니다. 이 숫자는 0 ≤ n ≤ 79에 대해 소수입니다.
• n# + 1 형식의 소수가 무한히 있습니까? (n#은 n보다 작은 모든 소수를 곱한 결과입니다)
• n# -1 형식의 소수가 무한히 있습니까?
• n 형태의 소수는 무한히 존재합니까? +1?
• n 형태의 소수는 무한히 존재합니까? - 하나?
• p가 소수이면 2 p -1은 항상 제곱 소수의 인수에 포함되지 않습니다.
• 피보나치 수열은 무한한 수의 소수를 포함합니까?

가장 큰 쌍둥이 소수는 2003663613 × 2 195000 ± 1입니다. 58711자리로 구성되며 2007년에 발견되었습니다.

가장 큰 계승 소수(n! ± 1 형식)는 147855입니다! - 1. 2002년에 발견된 142891자리의 숫자입니다.

가장 큰 원시 소수(n# ± 1 형식의 수)는 1098133# + 1입니다.

이 기사에서 우리는 공부할 것입니다 소수와 합성수. 먼저 소수 및 합성수의 정의를 제공하고 예를 제공합니다. 그 후, 우리는 소수가 무한히 많다는 것을 증명합니다. 다음으로 소수 테이블을 작성하고 소수 테이블을 컴파일하는 방법을 고려합니다. 특히 에라토스테네스의 체라고 하는 방법에 대해 자세히 설명합니다. 결론적으로 주어진 숫자가 소수 또는 합성임을 증명할 때 고려해야 할 주요 사항을 강조합니다.

페이지 탐색.

소수 및 합성수 - 정의 및 예

소수와 합성수의 개념은 1보다 큰 숫자를 나타냅니다. 이러한 정수는 양의 제수의 수에 따라 소수와 합성수로 나뉩니다. 그래서 이해하기 위해 소수 및 합성수의 정의, 제수와 배수가 무엇인지 잘 알고 있어야 합니다.

정의.

소수는 1보다 큰 정수로, 두 개의 양수 제수, 즉 자신과 1만 있습니다.

정의.

합성 숫자세 개 이상의 양수 제수가 있는 1보다 큰 정수입니다.

이와 별도로 숫자 1은 소수나 합성수에 적용되지 않습니다. 단위에는 숫자 1 자체인 양의 제수가 하나만 있습니다. 이것은 숫자 1을 적어도 두 개의 양의 제수가 있는 다른 모든 양의 정수와 구별합니다.

양의 정수가 이고 단위가 양의 제수를 하나만 갖는다는 점을 고려하면 소수 및 합성수의 음정 정의에 대한 다른 공식이 주어질 수 있습니다.

정의.

소수양의 제수가 두 개뿐인 자연수입니다.

정의.

합성수양의 약수가 2개 이상인 자연수입니다.

1보다 큰 모든 양의 정수는 소수 또는 합성수입니다. 즉, 소수도 합성도 아닌 단일 정수는 없습니다. 이것은 숫자 1과 숫자가 항상 모든 정수 a의 약수라고 말하는 나눗셈 속성에서 비롯됩니다.

이전 단락의 정보를 기반으로 합성 수에 대한 다음 정의를 제공할 수 있습니다.

정의.

소수가 아닌 자연수를 성분.

가지고 가자 소수 및 합성수의 예.

합성 수의 예로서 6 , 63 , 121 및 6697 을 제공합니다. 이 진술도 설명이 필요합니다. 양의 제수 1과 6 외에도 숫자 6에는 6 \u003d 2 3 이후 제수 2와 3도 있으므로 6은 실제로 합성 숫자입니다. 63의 양수 제수는 1, 3, 7, 9, 21, 63입니다. 숫자 121은 11 11의 곱과 같으므로 양의 제수는 1, 11 및 121입니다. 그리고 6697은 1과 6697 외에 양의 제수가 37과 181이기 때문에 합성수입니다.

이 단락의 결론에서 나는 또한 소수와 공소수가 같은 것과는 거리가 멀다는 사실에 주의를 기울이고 싶습니다.

소수 테이블

편의상 소수 추가 사용, 소수 테이블이라는 테이블에 작성됩니다. 아래는 소수 테이블최대 1000 .

논리적인 질문이 생깁니다. "왜 우리는 1,000까지만 소수의 표를 채웠고, 기존의 모든 소수의 표를 만드는 것이 불가능합니까?"

먼저 이 질문의 첫 번째 부분에 답해 보겠습니다. 소수를 포함하는 대부분의 문제의 경우 최대 1000개의 소수로 충분합니다. 다른 경우에는 특별한 솔루션 기술에 의존해야 할 가능성이 큽니다. 물론 10,000이든 1,000,000,000이든 상관없이 임의의 큰 유한 양의 정수까지 소수를 표로 작성할 수 있지만 다음 단락에서는 소수 표를 컴파일하는 방법에 대해 이야기할 것입니다. 특히, 그 방법을 분석할 것입니다. 라고 불리는.

이제 모든 기존 소수의 테이블을 컴파일하는 가능성(또는 오히려 불가능)을 살펴보겠습니다. 소수가 무한히 많기 때문에 모든 소수의 표를 만들 수는 없습니다. 마지막 진술은 다음의 보조정리 이후에 증명할 정리이다.

정리.

1이 아닌 1보다 큰 자연수의 가장 작은 양의 약수는 소수입니다.

증거.

허락하다 ㅏ - 자연수, 1보다 크며 b는 의 가장 작은 양의 비1 제수입니다. b가 소수임을 모순으로 증명하자.

b가 합성수라고 가정합니다. 그런 다음 1 및 b 모두와 다른 숫자 b의 제수가 있습니다(b 1이라고 표시합시다). 제수의 절대 가치가 배당의 절대 가치를 초과하지 않는다는 점도 고려한다면(우리는 이것을 나눌 수 있는 속성에서 알고 있습니다), 조건 1

숫자 a는 조건에 따라 b로 나눌 수 있고 b는 b 1로 나눌 수 있다고 말했기 때문에 나눗셈의 개념을 통해 a=b q 및 b=b 1인 정수 q 및 q 1의 존재에 대해 이야기할 수 있습니다. q 1 , 여기서 a= b 1 ·(q 1 ·q) . 두 정수의 곱은 정수이며, a=b 1 ·(q 1 ·q) 등식은 b 1 이 숫자 a 의 제수임을 나타냅니다. 위의 불평등을 고려하여 1

이제 우리는 소수가 무한히 많다는 것을 증명할 수 있습니다.