재밌는 문제 풀어보셈요(10.16)(1500덕)
간단한? 정수 문제입니다.
난이도 : 2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
고1 수학 0
고1,2모고 4등급입니다. 수상하12 모두 돌린상탠데 4등급이라 시발점으로...
-
오늘 역대급으로 어려운 내용가지고 통역하는데 죽는줄 알았네요 .. 흐어...
-
경희치 합격!! 8
-
가능인가요 저 05라 삼반수 한다면 07년생들이랑 만나는데..흠 군대도 가야하고
-
칸수 오르나요? ㅇㅇ?
-
막 공고같은곳이나.. ㅇㅇ 자기 지역 대학이나 서연고 서성한정도만 알던데
-
성대 글바메 거르고 갈만한가요? 수원인거 상관없는디 인터칼리지 어느정도에요?
-
텔그 중앙대 경영 95프로 됨
-
홍익대 합격생을 위한 노크선배 꿀팁 [홍대25][수강신청 기초가이드] 0
대학커뮤니티 노크에서 선발한 홍익대 선배가 오르비에 있는 예비 홍익대생, 홍익대...
-
자연 765.08 경영 754.24 정도면 자연대랑 상경 안정이라고 봐도 되려나...
-
과목별 세특을 다 전기정보공학이랑 엮어 쓰는게 맞겠죠?
-
두명이서 배부르게 먹을양인긴
-
대우 망한 뒤로 계속 하락하는 건가... 공부 좀 할 걸
-
경제 수특 없어서 이거라도 푸려는데 이거 개념 설명 ㄱㅊ음뇨..? 수특 배송 시키는건 귀찮은데..
-
중대 고대 빼곤 다 된건가요?
-
약간 어그로 ㅈㅅ 연대 지원할때 진학사를 안 사고 지원하는 경우도 있나요? 웬만하면...
-
중대식 점수 올랐는데 아직도 가망없나요..
-
4월입대라 가기전에는 사문 개념기출n제 마스터 하고가고싶은데 작년커리큘럼...
-
님들이라면 어디갑니까?집은 인하대가 더 가까워요
-
알려주세용
-
서성한도 모르는 사람 많음? 학창시절에 딱히 공부랑 관계없이 살았던 사람들
-
걍 몸만 갈까? 크리스마스인데 외출할때 코트 정도는 입어줘야 되는데
-
751.5면 써볼만 함??
-
ㅈㄱㄴ
-
오늘 한거 ㅇㅈ 36
혼자 갔다왔는데 하 진짜 커플들 멍많응요... 롯몰에서 혼밥하려다 쉽지 않아서 도망감요
-
이런 경우엔 나중에 좀 빠지나요? 전년도에 비해 경쟁률이 1.5배 정도 높아진 것 같습니다
-
빵나게?
-
수특 경제가 아니고 그냥 수능 경제책이 하나도 없다......
-
모르겠네
-
영1띄우면 갈 수 있는 대학 개수가 달라짐
-
8명 뽑는대ㅜ
-
높과가 높아서 빈건 보이는데 전체적으로 안찼는지는 모르겠던..
-
군 복무한 청년 '기후동행카드 할인' 최장 42세까지 연장 2
서울 대중교통 30일 무제한 이용권 5만5천원으로 할인 (서울=연합뉴스) 정수연...
-
보통은 맞겠지?
-
. 4
.
-
백분위 94 100인데 불변표가 유리한거죠?
-
4명 뽑는 소수관데 진학사는 7칸인데 메가스터디는 소신이라 떠요ㅠ 다군인데 확신은...
-
시간박치기 ㅈㄴ 해서 80프로 이상 푸는데 하나에 10분씩 걸리고 내가 글씨를...
-
21명 모집이고 1차, 2차 추합때 20명씩 빠졌습니다. 2차 추합까지 예비 없다가...
-
응응
-
한의사가 꿈은 아니지만 몇년동안 경한 목표였어서 ㅠ 만약 둘다 안정인데 하나만 써야된다면 인설의겠죠
-
. 2
.
-
씨발 존나아프네
-
전 수학은 문제에다가 부딪치면서 개념도 채화된다고 생각하는데 볼륨큰 개념강의로...
-
아.
-
기대된다
-
그냥 스스로 연밑고 인정하는 것 같은데요 ㅋㅋㅋ 다군 신설 영어 감점 조금만 하고...
-
느낌이 벌써부터 다르네 콘서타 가끔 진짜 ㅈㄴ 무서워 그보다 인데놀도 효과 좋네요
-
고민 더 해봐야 하긴 한데... 지거국에서 성적 잘 챙기고 열심히 하면 대학원 skp 갈만한가..?
-
나군에 갈 운명인가
가운데에 뭔기호에요?
a | b 에서 b가 a로 나누어 떨어진다는 의미입니다
이젠 님이 알려주시는군요..ㅋㅋ
이 문제 n<=2p 조건을 쓰면 간단한가요? ㅋㅋ 제 풀이는 이걸 안 썼는데 (어떻게 쓸지 모르겠어서..) 안 써서 그런가 좀 어려운 문제인 듯..
답은 (n,p) =(2,2), (3,3)이다.
i) 2|n
2|(p-1)^n+1 => p=2 =>n|2 => n=2.
ii) n은 홀수이고 p의 배수가 아님.
n의 최소 소인수를 q라고 하자. p-1이 q의 배수가 아님은 당연하다.
(p-1)^2n==1 (modq), (p-1)^(q-1)==1 (modq) (by 페르마 소 정리)
=> (p-1)^gcd(2n,q-1)==1 (modq) => (p-1)^2==1 (modq) (∵q는 홀수, (q-1,n)=1)
=> q|p(p-2)=>q|p-2 => p==2 (modq) (∵p와 q는 서로 다른 소수)
=> 0==(p-1)^n+1==1+1==2 (modq) => q=2 모순.
iii) n은 홀수이고 p|n.
v_p(n)=x라 하자.
Lifting the exponent lemma에 의해
x*(p-1)≤v_p((p-1)+1)+x => (p-2)x ≤ 1 => p≤3 => p=3 (∵x≥1)
=> n^2|2^n+1. 이는 imo 1990/P3이고, 답은 n=3 하나뿐이다.
따라서 구하는 모든 (n,p)는 (2,2), (3,3)이 전부이다.
오 맞아요 이제 봤네요.. 난도를 낮추기 위해 필요한 조건이랄까요 ㅋㅋ
쉽게푼 버전입니다
n^(p-1) | (p-1)^n + 1 이므로
n | n² | ... | n^(p-1) | (p-1)^n + 1
i) p가 n의 약수
p | (p-1)^n +1이므로 (-1)^n +1 = 0 (mod p)
1) n 짝수
2 = 0 (mod p)인 p = 2가 유일.
n^(p-1) | 2 이므로 n <= 2, 따라서 1 < n <= 2인 짝수 n은 2뿐.
2) n 홀수
n = pk <= 2p이므로 k = 1, n = p
따라서 준 식 p^(p-1) | (p-1)^p + 1
한편
(p-1)^p + 1
= pCp p^p - pC(p-1) p^(p-1) + pC(p-2) p^(p-2) - ... - pC2 p² + pC1 P - 1 + 1
= p² (pCp p^(p-2) - pC(p-1) p^(p-3) + ... - pC2 + 1) = f(p)
p | pCi 이므로 p² | f(p)이고 p³ !| f(p)
따라서 홀수 p는 3이 유일, 이때 n = 3
ii) p가 n의 약수 x
{n, n², ..., n^(p-1)} = {1, 2, ..., p-1} (mod p)
따라서 (p-1)! = (p-1)^n + 1 (mod p)
이때 (p-1)! = p-1 (mod p) 이므로
p-1 = (p-1)^n + 1 = (-1)^n + 1 (mod p)
p > 2인 소수 p에 대해 p-1 != (-1)^n이므로 불가
(2, 2), (3, 3)
맞습니다!
윗댓 사진 풀이 참고해보세요!
저런 문제는 어디서 가져오는 건가요?
작성하신 글 보니 저런 거 종종 올리시는 것 같은데..
경시 변형하거나 대부분 제가 만듭니다
그렇군요 감사합니다
약간의 오타가 있네요
마지막줄 p-1 != (-1)^n + 1 (mod p)
내친 김에 1990 imo P3 제 풀이도 올려봅니다.
n^2|2^n+1
n=1이면 조건을 만족한다.
n>1일 때, n의 최소 소인수를 p라고 하자.
2^(2n)==1 (modp), 2^(p-1)==1 (modp) (by 페르마 소 정리)
=> 2^(2n,p-1)==1 (modp) => 2^2==1 (modp) (∵(n,p-1)=1)
따라서 p=3이다.
Lifting the exponent lemma에 의해
2*v_3(n)=v_3(n^2)≤v_3(2^n+1)=v_3(2+1)+v_3(n) => v_3(n)≤1 => v_3(n)=1
n=3t라 하자. (t는 3의 배수가 아니다.)
t>1이면 t의 최소 소인수를 q라고 하면,
8^(2t)==1 (modq), 8^(q-1)==1 (modq) (by 페르마 소 정리)
=> 8^(2t,q-1)==1 (modq) => 8^2==1 (modq) (∵(t,p-1)=1)
=> q|63 => q=7 (∵q≠3)
2^n+1을 7로 나눈 나머지는 2,3,5만 가능하므로 모순, => t=1 => n=3
n=3일 때 확인해보면 해가 됨을 알 수 있다.
따라서 구하는 n은 1,3.
오 aops에서 봤던 풀이랑 비슷해요
근데 위에 풀이에서
q|p-2인 경우에 왜 쌍둥이 소수여야만 가능한가요?
q와 p가 모두 소수여서요 2차니 나는 소수쌍을 쌍둥이 소수라고 해요
그건 아는데 p-2가 꼭 소수이진 않잖아요, p-2가 합성수이고, q가 p-2의 약수일 수도 있는거 아닌가요
아 그렇네요. 아무생각없이 풀다보니까 그렇게 됬군요. 수정해서 올릴게요..ㅋㅋ
제가 그 부분에서 잠깐 막혔었는데 그냥 제 풀이처럼,
p==2 (modq) => 2==(p-1)^n+1==0 (modq) => q=2로 처리하는게 젤 간단한 듯요
맞아요. 제가 쓴 풀이 위에구해논 mod 식을 이용하는게 젤 간편하긴 해요
추가적으오 최대공약수 쪽으로 풀어서 접근해서 되는지 해보고 있었습니다