정수론 수학 풀이 질문
-
게시물 수정 , 삭제는 로그인 필요
정수론 수학 풀이 질문
여러 방법이 있는데 정수론 관련 개념 없이 풀 수 있는 풀이는 다음과 같습니다.
7x≡-3≡-3+13×4≡49(mod 13)
=> x≡7(mod 13)
정수론 정석 풀이는 유클리드 알고리즘 풀이도 있으니 참고히세요!
이 문제는 정수론에서 유명한 문제 중 하나인 '페르마의 소정리'를 이용한 문제입니다.
페르마의 소정리는 다음과 같습니다.
만약 p가 소수이고, a가 p의 배수가 아니라면, a^(p-1) ≡ 1 (mod p) 입니다.
이 문제에서는 p=7, a=3으로 주어졌으므로, 페르마의 소정리를 이용하여 3^6 ≡ 1 (mod 7)임을 이용합니다.
따라서, 3^201 ≡ 3^(6*33 + 3) ≡ (3^6)^33 * 3^3 ≡ 1^33 * 27 ≡ 6 (mod 7) 이 됩니다.
따라서, 3^201을 7로 나눈 나머지는 6이 됩니다.
답변이 되움 되셨나요
답변확정 부탁드리며, 즐거운 날 보내세요.
주어진 문제에서는 $a$와 $b$가 양의 정수이며, $a$가 $b$로 나누어 떨어지는 경우를 고려해야 합니다. 이 경우 $a$를 $b$로 나눈 몫을 $q$라고 하면, $a = bq$가 됩니다.
이때 $a$와 $b$의 최대공약수를 $d$라고 하면, $d$는 $a$와 $b$의 공통된 약수 중 가장 큰 값입니다. 따라서 $d$는 $b$의 약수이기도 합니다. 그리고 $a$는 $b$의 배수이므로 $a$도 $b$의 약수입니다. 따라서 $d$는 $a$와 $b$의 공통된 약수 중 가장 큰 값이므로 $d$는 $b$의 약수 중 가장 큰 값입니다.
따라서 $d$는 $b$의 약수이며, $b$는 $d$의 배수이므로 $d$와 $b$의 최대공약수는 $b$와 같습니다. 따라서 $gcd(a,b) = gcd(b,a mod b)$가 성립합니다.
이를 이용하여 주어진 문제를 해결할 수 있습니다. 먼저 $a$와 $b$의 최대공약수를 구하기 위해 $a$를 $b$로 나눈 나머지를 구합니다. 이때 $a mod b$가 0이면, $b$가 $a$의 약수이므로 $b$를 반환하면 됩니다. 그렇지 않은 경우에는 $b$와 $a mod b$의 최대공약수를 구하면 됩니다. 이 과정을 반복하여 $a$와 $b$의 최대공약수를 구할 수 있습니다.
... 정수론 관련 개념 없이 풀 수 있는 풀이는 다음과 같습니다. 7x≡-3≡-3+13×4≡49(mod 13) => x≡7(mod 13) 정수론 정석 풀이는 유클리드 알고리즘 풀이도 있으니 참고히세요!
... 정수론 문제를 풀고 있는데 도저히 안풀리는 문제라서 올려봅니다.... 일단 답은 n=343이라고 나오긴 하는데 왜 이렇게 나오는지 풀이 부탁드려요...
풀이과정 부탁드려요! 감사합니다! 도움이 되셨다면 채택부탁드립니다.
풀이과정 부탁드립니다! 감사합니다! 2줄에 끝남.
1. 정수 i에 대하여 다음과 같은 집합을 정의한다. Si = {nㅣ100i <=n<100(i+1) } /100 i 이상입니다/ 집합 S0, S1, ..., S999 중에서 완전제곱수를 갖지 않는 집한은 몇개인가?...
맨 밑 a,b,c,문제 풀이점 알려주세요. .
다음 식에서 모든 정수 n 을 구하시오 1) S(n)=72 S는 n의 모든 양의 약수의 합 풀이 과정 상세히 부탁드립니다. 노가다 말고 좋은 방법이 없어 보입니다. S가...
... (500!=1X2X3X.......X499X500입니다..) 수학 전공자가 아니어서 풀이방법이 깔끔하지 못할테지만, 풀어보면, 다음과 같습니다. 먼저 나누어 떨어진다고...
... 들자면 k=2라고 두고 나면 3²≡1 (mod4) 인거고 n=k인 n=2 대입하면 (3²)²≡3⁴≡1(mod4) 입니다. 문제 전문을 같이 붙여주셔야 풀이에 더 큰 도움을 드릴 수 있을 듯 합니다.
... 세 수의 최대공약수가 1, 아무렇게나 고른 두 수 합이 나머지 한 수로 떨어질 때 A,B,C를 구해라 제 실력으로는 불가능해 보이지만 풀이 쉽게하는 법...