합동기호 =로 쓸게요
x = 1 (mod 3)
x = 2 (mod 5)
x = 3 (mod 7)
이런 식으로 되어있으면 기본적으로는
5 × 7 × s1 = 1 (mod 3)
3 × 7 × s2 = 1 (mod 5)
3 × 5 × s3 = 1 (mod 7) 을 만족시키는 s값들을 찾은 뒤에
x = 1× 5 × 7 × s1 + 2 × 3 × 7 × s2 + 3 × 3 × 5 × s3 (mod 105) 로 나타내잖아요
그러면 애초에
5 × 7 × s1' = 1 (mod 3)
3 × 7 × s2' = 2 (mod 5)
3 × 5 × s3' = 3 (mod 7) 을 만족시키는 s' 값들을 찾은 뒤에
x = 5 × 7 × s1' + 3 × 7 × s2' + 3 × 5 × s3' (mod 105) 로 나타내면 안 되나요?
제 생각으로는 s1' = s1, s2' = 2 × s2, s3' = 3 × s3일 테니까 될 거 같은데... 혹시 안 되는 경우가 있나요
x = 1 (mod 3)
x = 2 (mod 5)
x = 3 (mod 7)
이런 식으로 되어있으면 기본적으로는
5 × 7 × s1 = 1 (mod 3)
3 × 7 × s2 = 1 (mod 5)
3 × 5 × s3 = 1 (mod 7) 을 만족시키는 s값들을 찾은 뒤에
x = 1× 5 × 7 × s1 + 2 × 3 × 7 × s2 + 3 × 3 × 5 × s3 (mod 105) 로 나타내잖아요
그러면 애초에
5 × 7 × s1' = 1 (mod 3)
3 × 7 × s2' = 2 (mod 5)
3 × 5 × s3' = 3 (mod 7) 을 만족시키는 s' 값들을 찾은 뒤에
x = 5 × 7 × s1' + 3 × 7 × s2' + 3 × 5 × s3' (mod 105) 로 나타내면 안 되나요?
제 생각으로는 s1' = s1, s2' = 2 × s2, s3' = 3 × s3일 테니까 될 거 같은데... 혹시 안 되는 경우가 있나요
맞긴 한데 s1, s2등의 잉여역수 계산을 유클리드 호제법으로 하기때문에 s2'을 찾는게 s2 구하고 두배하는 방법으로 찾게됨. 물론 찍어서 찾으려면 애초에 저방법 이전에 바로 암산으로 5 7 합성한 담에 3 합성하는 순서로 하는게 빠름
아 계산을 유클리드 호제법으로 하는거였구나 감사합니다!
예를들어 저 문제라먼 음.. 뒤에서부터 3 10 17에서 되네. 그럼 17 mod 35니까 17, 17+35=52에서 되네. 52 mod 105구나 하고 계산하는게 빠르지
모듈러계산 익숙하면 호제법까지 가지 말고 대충 암산으로 하셈 - dc App
애초에 식이 몇개 안될때는 첫번째 합동식에서 x=3n+1로 두고 두번째 합동식에 넣고 그거 푼 다음에 다시 세번째 식에 넣는게 빠름