일차합동식 ax ≡ b (mod n) 해 계산기

gcd(a, n)이 b를 나누면 해가 있고, 나누지 않으면 해가 하나도 없습니다. 좌변 ax를 n으로 나눈 나머지는 언제나 gcd(a, n)의 배수이기 때문입니다. 예를 들어 4x ≡ 5 (mod 12)는 좌변이 늘 짝수라 홀수 5가 될 수 없어 해가 없습니다.

해가 있다면 법 n 안에서 정확히 gcd(a, n)개입니다. 4x ≡ 8 (mod 12)은 gcd가 4라 해가 2, 5, 8, 11 넷입니다. 「해가 있으면 하나」라고 넘겨짚기 쉽지만 그것은 gcd가 1일 때만 맞는 말입니다.

n ÷ gcd 간격으로 고르게 놓입니다. 양변과 법을 gcd로 나눈 축약식 a′x ≡ b′ (mod n′)은 해가 딱 하나(x₀)인데, 법 n에서 x ≡ x₀ (mod n′)를 만족하는 수가 x₀, x₀+n′, x₀+2n′ … 로 gcd개 있기 때문입니다.

역원 계산기는 b = 1인 특수한 경우만 다룹니다. ax ≡ 1 (mod n)은 gcd가 1이어야 풀리고 해도 하나뿐이라, 해가 여러 개인 일반형은 다루지 않습니다. 이 계산기는 b가 무엇이든, gcd가 1이 아니어도 해 전체를 냅니다.

ax ≡ b (mod n)은 ax − ny = b라는 일차 부정방정식과 같은 말이므로 확장 유클리드 한 번이면 끝납니다. 양변과 법을 g = gcd(a, n)으로 나눠 a′x ≡ b′ (mod n′)로 만들면 gcd(a′, n′) = 1이라 a′의 역원이 반드시 있고, x₀ = b′ × (a′의 역원) mod n′이 가장 작은 해입니다.

됩니다. 0·x ≡ b (mod n)은 gcd(0, n) = n이므로 n이 b를 나눌 때만 해가 있고, 그때는 해가 n개 — 즉 모든 x가 해입니다. 규칙에 예외를 두지 않아도 그대로 맞아떨어지는 경계값이라 테스트로 고정해 두었습니다.

중국인의 나머지 정리 계산기를 쓰면 됩니다. 이 계산기는 식 하나를 푸는 것이고, x ≡ 2 (mod 3)과 x ≡ 3 (mod 5)처럼 여러 식을 동시에 만족하는 x를 찾는 것은 별도의 계산입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.