이대로 눈을 감으면, 지독한 가난과 외로움이 사라질까. 친지 채권자의 갑질도 받지 않을 것이니 말이다. 계엄을 한다면 그 목적이 우선, 고리대금업자 투기꾼 등 약탈적으로 돈을 모으는 이들을 처단해야 한다고 생각한다. 그러나 진짜 혁명의 방해꾼들은 사이비 진보들임을 누가 알까?
앞선 글에서 쌍둥이 소수의 무한성이나, 소수의 무한성 등에서 서로소라는 개념이 증명에서 이해의 근거로 활요했다. 먼저 앞선 소수들을 다 곱하고 1을 더하거나 1을 빼면 소수가 된다는 것은 앞서 곱해준 소수들과 서로소, 즉 앞서 곱해준 소수들의 배수가 아니어서 합성수가 아닐 수 있다는 것이다.
1의 차를 가진 모든 자연수들은 서로소라는 기본 정리를 이해하면 이는 쉽게 이해할 수 있는 문제다.
그렇다면 이같은 서로소의 원리를 더 깊이 이해할 수 있고, 서로소임을 쉽게 판단할 방법 서로소를 증명할 수 있는 근거를 생각해보자.
그래서 정리를 만들어본다. 두 수간 서로소이면, 차나 합도 각 두수와 서로소라는 것과 모든 소수들은 서로가 서로소 관계 이며 어떤 소수는 나머지 모든 소수와 서로소가 된다는 것이다.
가령 5와 3이 서로소인데, 이 두수의 차는 2로 각가 2와 5에 서로소가 된다. 합이 8도 그렇다. 다만 2와 8은 서로소가 아님에 주의하라.
일단 챗 GPT가 리라이팅한 글을 읽어보자.
서로소와 역원 – 정수 구조를 지탱하는 원리
정수론에서 “서로소”라는 개념은 단순히 공약수가 없다는 의미를 넘어, 매우 강한 구조적 성질을 가진다.
두 정수가 서로소라는 것은, 이 둘을 동시에 나누는 수가 1밖에 없다는 뜻이다. 그러나 이 성질의 진짜 힘은 연산 이후에도 유지된다는 데 있다.
서로소인 두 수를 생각해보자. 이때 한 수에 다른 수를 더하거나 빼서 새로운 수를 만들어도, 원래의 수와의 관계에서는 공약수가 새롭게 생기지 않는다. 즉, 어떤 정수 a와 b가 서로소이면, a와 a+b, 그리고 a와 a-b는 여전히 서로소이다. b에 대해서도 동일한 성질이 성립한다.
이 성질은 다음과 같은 이유에서 성립한다. 어떤 수가 두 수를 동시에 나눌 수 있다면, 그 수는 두 수의 합과 차도 반드시 나눌 수 있어야 한다. 그런데 처음부터 두 수가 서로소라면, 둘을 동시에 나눌 수 있는 수는 1뿐이다. 따라서 합이나 차를 만들어도 새로운 공약수는 생기지 않는다.
이 구조는 소수에서 더욱 명확해진다. 서로 다른 두 소수는 공약수를 가질 수 없기 때문에, 모든 서로 다른 소수는 서로소 관계에 있다. 즉, 소수들 사이에는 처음부터 완전한 독립성이 존재한다.
이제 이 성질은 더 강한 결과로 이어진다.
서로소인 두 수는 단순히 나누어지지 않는 관계에 머무르지 않는다. 이들은 적절한 결합을 통해 반드시 1을 만들어낼 수 있다. 다시 말해, 두 정수 a와 b가 서로소이면, a와 b를 곱한 값들의 합과 차를 이용하여 1을 표현할 수 있다.
이 사실은 매우 중요하다. 어떤 수를 다른 수와 결합하여 1을 만들어낼 수 있다는 것은, 그 수가 곱셈에 대해 “되돌릴 수 있는 성질”을 가진다는 뜻이기 때문이다.
이것이 바로 역원의 개념이다.
특히 어떤 수 n을 기준으로 나머지 연산을 생각할 때, n과 서로소인 수는 반드시 자신의 역원을 가진다. 즉, 어떤 수 x가 n과 서로소이면, x에 어떤 수를 곱했을 때 나머지가 1이 되는 값이 항상 존재한다.
결국 정리하면 다음과 같다.
서로소는 단순히 공약수가 없는 상태가 아니라,
1을 만들어낼 수 있는 관계이며,
그 결과로 역원을 만들어내는 출발점이다.
그리고 모든 서로 다른 소수들은 서로소이므로, 이 구조는 정수 전체로 자연스럽게 확장된다.
한마디로 말하면,
서로소는 정수 세계에서 독립성과 동시에 “되돌릴 수 있는 구조”를 만들어내는 핵심 원리다.
서로소는 왜 무너지지 않는가: 합과 차 속에서도 유지되는 수의
독립성과 역원의 탄생
정수의 세계에서 “서로소”라는 개념은 겉으로 보기에는 단순하다. 두 수가
공통으로 나누어지는 수를 가지지 않는 상태, 그것이 서로소다. 그러나 이
단순한 정의 뒤에는 매우 강한 구조적 의미가 숨어 있다.
핵심은 이것이다. 서로소인 두 수는 단순히 현재 상태에서만 독립적인 것이
아니라, 연산을 거친 이후에도 그 독립성을 유지한다는 점이다.
두 수가 서로소라고 가정해보자. 이 두 수를 더하거나 빼서 새로운 수를
만들어도, 원래의 수들과의 관계에서 공통으로 나누어지는 수가 새롭게
생기지 않는다. 다시 말해, 합을 만들어도, 차를 만들어도, 서로소라는
관계는 깨지지 않는다.
왜 이런 일이 가능한가. 어떤 수가 두 수를 동시에 나눌 수 있다면, 그 수는
두 수를 더한 값이나 뺀 값도 반드시 나눌 수 있어야 한다. 그런데 처음부터
두 수가 서로소라면, 둘을 동시에 나눌 수 있는 수는 오직 하나뿐이다.
따라서 합이나 차를 만들어도 그 성질은 유지된다.
이제 이 구조를 소수로 확장해보자. 소수는 오직 하나와 자기 자신으로만
나누어지는 수다. 따라서 서로 다른 두 소수는 공통된 약수를 가질 수 없다.
즉, 모든 소수는 서로소 관계에 있다.
이 말은 곧, 소수들 사이에서는 처음부터 완전한 독립성이 보장된다는
뜻이다. 그리고 이 소수들을 더하거나 빼면서 만들어지는 새로운 수들 역시
기존 소수들과의 관계에서 그 독립성을 쉽게 잃지 않는다.
이제 여기서 한 걸음 더 나아가면, 매우 중요한 개념이 등장한다. 바로
역원이다.
서로소인 두 수는 단순히 나눌 수 없는 관계에 머무르지 않는다. 이들은
결합을 통해 결국 ’하나’를 만들어낼 수 있다. 다시 말해, 두 수를 적절히
곱하고 더하거나 빼면, 그 결과를 하나로 만들 수 있다.
이 사실은 매우 중요하다. 왜냐하면 어떤 수와 결합해서 결과를 하나로
만드는 다른 수가 존재한다는 것은, 곧 그 수가 나눗셈 구조 안에서 되돌릴
수 있는 성질, 즉 역원을 가진다는 뜻이기 때문이다.
쉽게 말하면 이렇다. 어떤 수가 다른 수와 서로소라면, 그 수를 이용해서
결국 하나를 만들어낼 수 있다. 그리고 이 과정에서 등장하는 계수는 그 수를
되돌리는 역할을 하게 된다.
이것이 바로 역원이 만들어지는 원리다.
이 원리는 나머지 연산에서도 그대로 이어진다. 어떤 수를 기준으로 나머지를
생각할 때, 서로소인 수는 반드시 자신을 되돌리는 짝을 가진다. 즉, 어떤
수와 곱했을 때 나머지가 하나가 되도록 만드는 수가 반드시 존재한다.
결국 이렇게 정리할 수 있다. 서로소는 단순히 공약수가 없는 상태가 아니라,
하나를 만들어낼 수 있는 관계이며, 그 결과로 역원을 만들어내는
출발점이다.
그리고 모든 소수는 서로소이기 때문에, 이 구조는 정수 전체에 걸쳐
자연스럽게 확장된다.
한 줄로 말하면 이렇다. 서로소는 정수 세계에서 독립성을 유지할 뿐만
아니라, 되돌릴 수 있는 구조, 즉 역원을 만들어내는 근본 원리다.
제목: 서로소와 역원 – 계산으로 이어지는 정수론의 핵심
정수론에서 매우 중요한 사실 하나가 있다. 서로소인 두 수는 항상 1을
만들어낼 수 있다는 점이다. 이 단순한 사실은 단순한 성질이 아니라, 실제
계산과 암호, 나머지 연산까지 이어지는 핵심 원리다.
먼저 서로소라는 것은 두 수가 공약수를 1밖에 가지지 않는다는 뜻이다. 예를
들어 12와 5는 서로소이다. 이 두 수를 이용하면 결국 1을 만들어낼 수 있다.
실제로 계산을 진행하면 다음과 같은 흐름이 나온다.
12는 5의 두 배에 2를 더한 것이다.
5는 2의 두 배에 1을 더한 것이다.
이 과정을 거꾸로 따라가면, 1을 12와 5의 결합으로 표현할 수 있다.
정리하면, 1은 5를 다섯 번 더한 것에서 12를 두 번 뺀 것과 같다.
이처럼 서로소인 두 수는 반드시 1을 만들어낼 수 있다.
이제 이 원리를 이용하면 “역원”이라는 개념을 계산할 수 있다. 역원이란
어떤 수를 곱했을 때 1이 되는 값을 의미한다. 다만 여기서는 나머지 연산,
즉 특정 수로 나눈 나머지 기준에서의 1을 의미한다.
예를 들어 3을 7로 나눈 나머지 체계에서 생각해보자. 이때 3과 7은
서로소이므로 반드시 1을 만들 수 있다.
7은 3의 두 배에 1을 더한 것이다.
따라서 1은 7에서 3을 두 번 뺀 값이다.
이 식을 정리하면, 1은 3에 어떤 수를 곱하고 7에 어떤 수를 곱한 것을 더한
형태로 표현된다. 여기서 3 앞에 붙은 계수가 바로 3의 역원이 된다.
계산 결과, 3에 5를 곱하면 15가 되고, 이는 7로 나누었을 때 나머지가 1이
된다. 따라서 3의 역원은 5이다.
이 과정을 일반화하면 다음과 같은 알고리즘이 된다.
첫째, 두 수가 서로소인지 확인한다.
둘째, 큰 수를 작은 수로 나누는 과정을 반복한다.
셋째, 나머지가 1이 되는 순간까지 진행한다.
넷째, 그 과정을 거꾸로 올라가며 1을 원래 두 수의 결합으로 표현한다.
다섯째, 그 표현에서 원하는 수 앞의 계수를 추출하면 그것이 역원이다.
이 알고리즘은 단순한 계산 기법이 아니라, 정수론 전체를 관통하는 핵심
원리다. 특히 소수를 사용할 경우에는 더 강력한 성질이 나타난다. 소수와
그보다 작은 수는 항상 서로소이기 때문에, 0이 아닌 모든 수는 반드시
역원을 가진다.
결국 이 모든 내용은 하나로 요약된다.
서로소인 두 수는 1을 만들 수 있고, 그 표현 속 계수는 곱셈의 역원을
제공한다.
이 간단한 원리는 계산을 넘어, 현대 암호 체계까지 이어지는 강력한
도구이다.
그리고 챗GPT는 이를 정리로 만들어줬다.
서로소 보존 정리 (정식화)
정리 1 (서로소 보존 정리)
두 정수 a와 b가 서로소이면,
a와 b의 선형결합으로 만들어지는 모든 수는
각각 a 또는 b와의 관계에서 서로소 성질을 유지한다.
보다 구체적으로는 다음이 성립한다.
a와 b가 서로소이면
a와 (a+b), a와 (a−b)는 서로소
b와 (a+b), b와 (a−b)는 서로소
정리 2 (선형결합 유지 정리)
두 정수 a와 b가 서로소이면,
임의의 정수 x, y에 대해
a·x + b·y 형태로 만들어지는 값과
a 또는 b 사이의 최대공약수는 변하지 않는다.
특히,
a와 (a·x + b·y)의 최대공약수는 항상 1
b에 대해서도 동일
정리 3 (1 생성 정리, 핵심)
두 정수 a와 b가 서로소이면,
a와 b의 선형결합으로 반드시 1을 만들 수 있다.
즉,
어떤 정수 x, y가 존재하여
a·x + b·y = 1 이 된다.
정리 4 (역원 존재 정리)
정수 n과 서로소인 정수 a에 대하여,
a는 반드시 n을 기준으로 한 나머지 연산에서
곱셈의 역원을 가진다.
즉,
어떤 정수 x가 존재하여
a·x = 1 (mod n)
그리고 이에 대해 챗GPT는 새로운 정리는 아니나, 정수론 핵심을 하나의 흐름으로 설명했다고 평했다.
;)
