[일반] 경시 수학문제 질문드려요

[익명(115.140)]

2^80+1은 합성수인가? 소수인가?

이런 문제는 도대체 어떻게 푸는건가요?

소수 판정법을 암기라도 해야되는건지 아니면 일일이 세는건지

[디피프(dlffff)]

뭐 대체로 합성수일테고 a^(p-1)=1 인거나 인수분해를 하거나 해서 어떤 수로 나눠지는지 찾으면 될듯. 위 문제는 80=16*5 에서 끝

[익명(115.140)]

? 이해가 안되는데..

[디피프(dlffff)]

x^5+1 = (x+1)(x^4-x^3+x^2-x+1)

[익명(115.140)]

ㄷㄷ 그럼 합성수임을 증명하는거 말고, 소수임을 증명하는건 일일이세는게 답인가요?

[익명(110.70)]

https://en.wikipedia.org/wiki/Fermat_number?wprov=sfla1
홀수소수라면 페르마수꼴이어야 하고 소수인 페르마수 찾는 법은 아직 안풀림

[디피프(dlffff)]

다항시간내에 소수 판정하는 알고리즘 같은거 있었을건데 사람이 할만한 계산은 아닐걸

[ㅅㄲㅁㅇ(as1392)]

https://en.m.wikipedia.org/wiki/Primality_test

[익명(115.140)]

구간이 주어지고 그 구간에 속한 소수의 개수가 1000개 이상임을 증명하는 문제에요. 구간이 너무나도 크게 주어져서 (2^2^1000) 그 안에 소수가 1000개 있음은 당연할건데, 이걸 증명하자니방법이 없네요. 프로그램으로 푸는 문제도 아니고요..

[ㅅㄲㅁㅇ(as1392)]

개수만 중요하면 소수정리 관련 결과쓰면 될텐데. 아니 수가 너무 커서 베르트랑 공준만 써도 될듯

[익명(175.223)]

오이오이 경시수학이라구

[익명(115.140)]

베르트랑 공준? 이건 내용만 알고있으면 바로 풀리긴하네요. 증명이어렵네요 ㅠ

[익명(175.223)]

n번째 소수 <= 2^2^n이라는걸 증명하면 되지 않을까

[익명(175.223)]

귀납법으로 가정하면 p_(n+1) <= p_1p_2...p_n +1 <= 2^2*2^4*...*2^2^n +1=2^(2+4+16+...+2^n)+1 <2^(2(2^n-1))+1 <2^2^(n+1)으로 증명하면 될듯

[기괴공학도(mecheng98)]

[익명(115.140)]

p_(n+1) <= p_1p_2...p_n +1 <= 2^2*2^4*...*2^2^n +1=2^(2+4+16+...+2^n)+1 이거 어떻게 나온거야?

[익명(115.140)]

n+1 소수가 그 전 모든 소수의 곱+1보다 크다라는거랑 n번째 소수가 2^2^n보다 작다라는건 어케 증명했음?

[기괴공학도(mecheng98)]

각각 귀류법이랑 귀납법으로 보일 수 있을 것 같아요

[익명(175.223)]

2+4+16+...이 아니라 2+4+8+16+...

[익명(175.223)]

유클리드식 소수의 무한성 증명할때 모티베이션 주잖어

[익명(115.140)]

모티베이션 뜻이 뭔가요? 그리고 무한성 증명은 n+1번째 소수가 그 전소수의 곱이다. 혹은 크다. 라는 증명이 아니지 않나요?

[익명(175.223)]

동기부여/ 소수가 n개까지 밖에 없으면 그 전까지의 소수로 안나눠지잖아 그러면 더 큰 수로 나눠져야 할 거 아니야 당연히 더 큰소수는 p1p2...pn+1보다는 작을거고

[익명(175.223)]

그리고 pn < 2^(2^n)은 귀납법가정이고 이로부터 p_(n+1)<2^2^(n+1)이 성립하고 수학적귀납법에 의해 모든n에 대해서 성립

[익명(115.140)]

제가 궁금한게 그 귀납법 가정이라는게 틀릴수 있지 않나라는거에요. 물론 직관도 그렇고 이미 소수를 어떻게든 공식화해서 만들었기때문에 그거랑 비교해보면 당연히 성립함은 알겠는데, 고교과정에서 그 가정이 100% 답이라는 확실은 못내지 않나요? 그리고 당연히 n+1 번째 소수가 p1...pn보다는 작을 것이다라고 했는데 이것도 직관으로 봐야하는거죠?

[익명(119.199)]

이건 귀납법을 다시 배워야된다

[ㅅㄲㅁㅇ(as1392)]

n=1일때는 할 수 있잖아... 귀납적 가정 자체를 어케 생각하느냐를 묻는거면 몰라도

[익명(175.223)]

p_(n+1) <= p1p2...pn +1인것 같다는 건 직관이지만 성립한다는 건 증명에 의한 결과지

[ㅅㄲㅁㅇ(as1392)]

그냥 1000개 이하라고 가정하고 얘들은 2^1000번 이하로 곱해져야 원하는 범위의 수를 구할 수 있고 경우의수 써서 해보면 원하는 범위의 수가 2^2^1000보다 작기때문에 모순 이정도로도 괜찮을듯

[마역문화(icenight0)]

저건 경시는 커녕 고등 수학 기초 인거 같은데.