합동 (Congruence)

합동 관계 (congruence relation)
※ LaTeX으로 합동을 표기할 때는 \equiv 를 사용하고, modulo는 \mod{m} 또는 \pmod{m} 를 사용한다.
다음 세 문장은 동치이다.
인 정수 가 존재한다. 이고 를 만족하는 정수 가 존재한다.
그리고 다음이 성립한다.
특히
, ,
서로 합동이라면, 덧셈, 곱셈, 거듭제곱에서도 합동관계가 보존된다.
Example
한편
따라서
다항식에서의 합동
정수 계수를 갖는 다항식이 다음과 같다고 하자.
그리고 양의 정수
이면
3의 배수와 9의 배수 판정
초등학교때 "모든 자릿수의 수를 더한 수가 3의 배수이면, 원래 수도 3의 배수이다"
또는 "모든 자릿수의 수를 더한 수가 9의 배수이면, 원래 수도 9의 배수이다"를 배웠다.
위에서 설명한 다항식에서의 합동을 이용하여 증명할 수 있다.
우리가 사용하는 수 체계가 10진법임을 이용한다.
높은자리부터 표기하므로
모든 자릿수의 합은
한편,
따라서 만약
9의 배수도 동일하게 증명할 수 있다.
11의 배수도 비슷하게 증명할 수 있다.
낮은 자리수부터 차례대로 더하고 뺀 수를
합동에서의 나눗셈 (Division in Congruence)
그렇다면 그 역도 성립하는가?
NO! 그렇지 않다.
다음이 성립한다.
따라서, collorary로
그리고 항등식과 다른 성질을 갖는다. 특히,
반례)
'스터디 > 알고리즘' 카테고리의 다른 글
[Python] 고대 문명 유적 탐사: 삼성SW역량테스트 2024 상반기 오전 1번 (0) | 2024.10.13 |
---|---|
[Python] 코드트리 투어: 삼성SW역량테스트 2024 상반기 오전 2번 (0) | 2024.09.21 |
[Python] 루돌프의 반란: 삼성SW역량테스트 2023 하반기 오후 1번 (0) | 2024.09.20 |
최소 공통 조상 (Lowest Common Ancestor, LCA) (0) | 2024.07.11 |
[Python] 퍼즐 조각 채우기 (2) | 2024.07.03 |