[일반] 쉬운 정수론 문제낸다

[익명(220.90)]

X=a(mod m) , x=b(mod n) m,n은 1보다 큰 자연수일때

위 연립 방정식의 해가 존재할 필요 충분 조건은

a=b(mod gcd(m,n) ) 임을 증명해라

이거 쉬운데 풀수 있으려나

[극한의권마태수(snail2149)]

못품

[수갤러 1(121.173)]

위 방정식의 해가 존재 <=> 적당한 정수 s, t가 존재하여 ms + a = nt + b <=> 적당한 정수 s, t가 존재하여 ms - nt = b - a <=> (베주 항등식에 의해) gcd(m, n)|(b-a)

[익명(220.90)]

오 이정도면 잘 푼거네 아니 나는 직접 mod 식을 풀어서 설명하는게 좋은데 이 풀이도 개 깔끔하네

[s&p50(dart8913)]

이건 자명한 문제 같은데. gcd =1 일때는 중국에서 성립, 일반케이스는 쉬프트하고 나서 gcd로 나누면 바로 따라나옴

[전기도둑(1.254)]

못풀겠어서 GPT 도움을 조금 받음

[전기도둑(1.254)]

간단한 증명 mk+a=nk+b \;\Longrightarrow\; (m-n)k=b-a. 따라서 k\mid(b-a), 곧 b\equiv a\pmod{k}. 또는 같은 등식을 양변을 k로 나눈 나머지 관점에서 보면 mk+a\equiv a\pmod{k},\quad nk+b\equiv b\pmod{k}, 이므로 a\equiv b\pmod{k}.