빨간 줄 부분이 이해가 안되네요...
일단 9x ≡ 21 (mod 30)에서, ≡의 양변의 공통인수 3을 나누고 mod는 gcd(3,30)=3으로 나눠서 다음의 동치식을 얻고
3x ≡ 7 (mod 10). 여기에서는 법 10에 대한 3의 곱셈 역원 7을 곱해서
21x ≡ x ≡ 49 ≡ 9 (mod 10), 즉 x ≡ 9 (mod 10)을 얻는 것까지는 이해했습니다.
1. 빨간 줄 부분이 위의 과정이랑 무슨 상관이 있나요? 이해가 안돼서 갑툭튀한 것 같은 느낌이 드네요.
2. 각 수 0·3, 1·3, 2·3, ..., 9·3은 실제로 곱해보고 10으로 나눈 나머지가 0,3,6,9,2,5,8,1,4,7임을 통해 법 10에 대한 완전 잉여계임은 확인했는데
이렇게 직접 곱해서 10으로 나눠봐야만 완전잉여계인지 알 수 있나요?
3. 아무튼 완전잉여계이니 0·3, 1·3, 2·3, ..., 9·3 중의 하나는 법 10에 대해 1과 합동이겠죠. 근데 이 말이 왜 갑자기 나온건가요? 앞뒤 문장이랑 무슨 관계인지
모르겠습니다.
이 댓글은 게시물 작성자가 삭제하였습니다.
3x=7 (mod10)과 21x=49 (mod10)의 해집합이 완전히 동일하다는 것이 중요합니다. 예를 들어 합동식 3x=7 (mod10)에 7이 아닌 5를 곱한다면 15x=35 (mod10)이 될 것이고, 5|15, 5|35, 5|10이므로 이는 3x=7 (mod2)와 동치이며 이의 해집합은 x=1,3,5,7,9 (mod10)으로 기존에 구하려던 합동식 3x=7 (mod10)의 해집합 x=9(mod10)을 포함합니다. 이런 현상이 발생하는 이유는 5가 10과 서로소가 아니여서 합동식에 5를 곱할 시 약분이 되어 기존에 구하려던 해 이외의 다른 해까지 구하게 되어버리기 때문입니다.
한편 10과 서로소인 임의의 수는 법 10에 대해 역원이 존재합니다. 책에서 나온 예시인 7은 10과 서로소이고, 7의 법 10에 대한 역원 3이 존재하므로 ax=b (mod10)의 해집합은 7ax=7b (mod10)의 해집합과 동일합니다. 왜냐하면 7ax=7b (mod10)에 7의 역원인 3을 양변에 곱하면 다시 ax=b (mod10) 이 되기 때문입니다.
이는 완전잉여계에 어떤 수를 곱해야 다시 완전잉여계가 되는가에 대한 질문에 대한 답이 되기도 합니다. 만약 (a,n)=1 이고 a의 법n에 관한 역원이 a*라 할 때, 완전잉여계의 서로 다른 두 원소 b, c에 대해 ba = ca (mod n)라 가정하면 a의 역원이 존재하므로 baa*=caa*=c=b (mod n) 가 되어 모순입니다. 즉 완전잉여계는 각 원소에 n의 서로소를 곱해도 완전잉여계가 됩니다
자세한 답변 감사합니다. 첫댓은, 제가 생각하기에는 질문드렸던 부분이 아닌 것 같지만 그래도 전혀 생각하지 못했던 부분입니다. 법 n과 서로소이건 아니건 합동식에 얼마든지 곱하든 나누든(나누는 경우에 한해 mod는 gcd로 나누어질 수 있음) 부수 효과가 없을 거라고 은연 중에 생각하고 있었는데 아니었네요. a≡b (mod n)이면, ac≡bc (mod n) ca≡cb (mod n)이면, a≡b (mod n/d), where d=gcd(c,n) 답변을 다 이해하지 못해서 조금 더 봐야 할 것 같습니다. 감사합니다.
법과 서로소가 아니면 역원이 존재하지 않아서 차후에 약분하면서 법이 줄어들면 되돌릴 수 없는 식 변환이 됨(그 말은 약분하지 않는 한 문제는 안됨). 또한 약분하면서 법이 줄어들고 나중에 다시 법을 원래대로 되돌리는 과정에서 해의 갯수가 늘어날 수 있음. 이 때는 원래의 식에 대입해서 따로 확인하는 과정이 필요함.
0·3, 1·3, 2·3, ..., 9·3 이 내용 관련해 제가 파악한 바로는, 추측이지만, 각 수에 곱해진 3은 법 10에 대하여 역원 7을 가집니다. 따라서 각각에 7을 곱하면 차례로 각각은 0,1,2,3,...,9이 됨을 알 수 있습니다. 즉 완전 잉여계입니다.
네 정확하십니다. 어제 먼가 답변을 좀 두루뭉술하게 한 것 같은데.. 죄송합니다. 책에서 말하고자 하던 건, (3,10)=1이므로 합동식 3x=7 (mod10)를 간단히 히기 위해 3의 법10에 관한 역원 7을 찾아 의도적으로 곱하여 x의 계수를 1로 만들어주는 테크닉이 가능하다는 걸 말하려 했던 듯 합니다
많은 도움이 되었습니다. 감사합니다. 앞선 코멘트에서 제가 '약분하지 않는 한 문제는 안됨'라고 했었는데 법과 서로소 아닌 정수를 곱하는 것만으로도 해가 바뀌기도 하는군요. 3x≡7 (mod 10)의 해는 x≡9 (mod 10)이지만, 양변에 2를 곱했을 때 별도의 약분없이도 6x≡14 (mod 10)의 해는 x≡4, 9 (mod 10)