Coprime integers

수학(mathematics)에서, 두 정수(integer) $a$ 와 $b$ 는 만약 그것들의 둘 다의 약수(divisor)인 유일한 양의 정수가 1이면 서로소(coprime), 상대적으로 소수(relatively prime), 또는 서로 소수(mutually prime)입니다.^[1] 결과적으로, $a$ 를 나누는 임의의 소수(prime number)는 $b$ 를 나누지 않고, 그 반대도 마찬가지입니다. 이것은 그것들의 최대 공통 약수(greatest common divisor) (GCD)가 1인 것과 동등합니다.^[2] 우리는 역시 $a$ 가 $b$ 에 소수 또는 $a$ 는 $b$ 와 서로소라고 말합니다.

숫자 14와 25는 개별적으로 어떤 것도 소수로 고려되지 않음에도 불구하고 1이 그것들의 유일한 공약 약수이기 때문에 서로소입니다. 다른 한편으로, 14와 21은 그것들이 둘 다 7로 나뉠 수 떨어지기 때문에 서로소가 아닙니다. 축소된 분수(reduced fraction)의 분자와 분모는 정의에 의해 서로소입니다.

Notation and testing

상대적으로 소수 정수 $a$ 와 $b$ 에 대해 표준 표기법은 다음입니다: $gcd(a, b) = 1$ 와 $(a, b) = 1$ . 그들의 1989 교과서에서, 로널드 그레이엄(Ronald Graham), 도널드 커누스(Donald Knuth), 및 오렌 퍼타시닉(Oren Patashnik)은 표기법 $a\perp b$ 을 $a$ 와 $b$ 가 상대적으로 소수임을 나타내기 위해 사용하고 용어 "소수(prime)"를 ( $a$ 가 $b$ 에 소수임에서 처럼) 서로소 대신에 사용할 것을 제안했습니다.^[3]

두 숫자가 서로소인지 여부를 결정하기 위한 빠른 방법은 유클리드 알고리듬(Euclidean algorithm)과 이항 GCD 알고리듬(binary GCD algorithm) 또는 레머의 GCD 알고리듬(Lehmer's GCD algorithm)과 같은 그것의 더 빠른 변형에 의해 제공됩니다.

1과 $n$ 사이의 양의 정수 $n$ 과 서로소인 정수의 개수는, 역시 오일러의 파이 함수, $φ (n)$ 로 알려져 있는 오일러의 토션트 함수(Euler's totient function)에 의해 제공됩니다.

정수의 집합(set)은 역시 만약 그것의 원소가 1을 제외한 공통 양의 인수를 공유하지 않으면 서로소라고 불릴 수 있습니다. 정수의 집합 위에 더 강한 조건은 쌍별 공소수이며, 이것은 $a$ 와 $b$ 가 집합에서 다른 정수의 모든 각 쌍 $(a, b)$ 에 대해 서로소임을 의미합니다 집합 ${2, 3, 4$ }는 서로소이지만, 2와 4가 상대적으로 소수가 아니기 때문에 쌍별 서로소는 아닙니다.

Properties

숫자 1과 −1은 모든 각 정수와 서로소인 유일한 정수이고, 그것들은 0과 서로소인 유일한 정수입니다.

여러 조건은 $a$ 와 $b$ 가 서로소인 것과 동등한 것입니다:

$a$ 와 $b$ 둘 다를 나누는 소수(prime number)는 없습니다.
$ax + by = 1$ 를 만족하는 정수 $x$ 와 $y$ 가 존재합니다 (베주의 항등식(Bézout's identity)을 참조하십시오).
정수 $b$ 는 곱셈 역(multiplicative inverse) 모듈로 $a$ 를 가지며, $by \equiv 1 (mod a)$ 를 만족하는 정수 $y$ 가 존재함을 의미합니다. 링-이론적 언어에서, $b$ 는 정수 모듈로(integers modulo) $a$ 의 링(ring) $Z / a Z$ 에서 단위(unit)입니다.
형식 $x \equiv k (mod a)$ 와 $x \equiv m (mod b)$ 의 미지수 정수 $x$ 에 대해 합동 관계(congruence relation)의 모든 각 쌍은 해를 가집니다 (중국 나머지 정리(Chinese remainder theorem)); 실제로 그 해는 단일 합동 관계 모듈로 $ab$ 에 의해 설명됩니다.
$a$ 와 $b$ 의 최소 공통 배수(least common multiple)는 그것들의 곱 $ab$ , 즉, $lcm(a, b) = ab$ 와 같습니다.^[4]

세 번째 점의 결과로, 만약 a와 b가 서로소이고 br ≡ bs (mod a)이면, r ≡ s (mod a)입니다.^[5] 즉, 우리는 모듈로 a를 작업할 때 "b로 나눌 수" 있습니다. 더욱이, 만약 b₁과 b₂가 둘 다 a와 서로소이면, 그것들의 곱 b₁b₂도 마찬가지입니다 (즉, 모듈로 a 그것은 역가능 원소의 곱이고, 따라서 역가능입니다).^[6] 이것은 역시 유클리드 보조정리(Euclid's lemma)에 의해 첫 번째 점에서 비롯되며, 그 보조정리는 만약 소수 p가 곱 bc를 나누면, p는 인수 b, c 중 적어도 하나를 나눈다고 말합니다.

첫 번째 점의 결과로, 만약 a와 b가 서로소이면, 임의의 거듭제곱 a^k와 b^m도 마찬가지입니다.

만약 a와 b가 서로소이고 a가 곱 bc를 나누면, a는 c를 나눕니다.^[7] 이것은 유클리드의 보조정리의 일반화로 보일 수 있습니다.

Figure 1. The numbers 4 and 9 are coprime. Therefore, the diagonal of a 4 × 9 lattice does not intersect any other lattice points

두 정수 a와 b가 서로소인 것과 데카르트 좌표 시스템(Cartesian coordinate system)에서 좌표 (a, b)를 갖는 점이 원점과 (a, b) 사이의 선분 위에 어디에도 정수 좌표를 가진 점이 없다는 의미에서 원점(0,0)으로부터 방해받지 않는 시선을 통해 "보일" 것은 필요충분 조건입니다. (그림 1을 참조하십시오).

정확하게 만들어질 수 있는 의미에서, 무작위로 선택한 두 정수가 서로소일 확률(probability)은 $6/ π 2$ 이며, 약 61%입니다 (아래의, § Probability of coprimality를 참조하십시오).

두 자연수(natural number) a와 b가 서로소인 것과 숫자 2^a − 1과 2^b − 1가 서로소인 것은 필요충분 조건입니다.^[8] 이것의 일반화로, 밑수(base) n > 1에서 유클리드 알고리듬(Euclidean algorithm)에서 쉽게 비롯됩니다:

\gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.

Coprimality in sets

정수의 집합(set) S = {a₁, a₂, .... a_n}는 역시 만약 집합의 모든 원소의 최대 공통 약수(greatest common divisor)가 1이면 서로소 또는 집합별 서로소라고 불릴 수 있습니다. 예를 들어, 정수 6, 10, 15는 1이 그것들 모두를 나누는 유일한 양의 정수이기 때문에 서로소입니다.

만약 정수 집합의 모든 각 쌍이 서로소이면, 그 집합은 쌍별 공소수 (또는 쌍별 상대적 소수, 서로 서로소, 또는 서로 상대적 소수)라고 말합니다. 쌍별 서로소성은 집합별 서로소성보다 더 강력한 조건입니다; 모든 각 쌍별 서로소 유한 집합은 역시 집합별 서로소이지만, 그 반대는 참이 아닙니다. 예를 들어, 정수 4, 5, 6은 (집합별) 서로소이지만 (왜냐하면 그것들 모두를 나누는 유일한 양의 정수가 1이기 때문), 그것들은 쌍별 서로소가 아닙니다 (왜냐하면 gcd(4, 6) = 2이기 때문입니다).

쌍별 서로소성의 개념은 중국 나머지 정리(Chinese remainder theorem)와 같은 숫자 이론에서 많은 결과에서 가설로 중요합니다.

정수의 무한 집합(infinite set)에 대해 쌍별 서로소가 되는 것이 가능합니다. 주목할만한 예제는 모든 소수의 집합, 실베스터 수열(Sylvester's sequence)에서 원소의 집합, 및 모든 페르마 숫자(Fermat numbers)의 집합을 포함합니다.

Coprimality in ring ideals

교환 링(commutative ring) R에 있는 둘의 아이디얼(ideals) A와 B는 A + B = R이면 서로소 (또는 공동극대(comaximal))라고 불립니다. 이것은 베주의 항등식(Bézout's identity)을 일반화합니다: 이 정의와 함께, 정수 Z의 링에 있는 둘의 주요 아이디얼(principal ideal) (a)와 (b)가 서로소인 것과 a와 b가 서로소인 것은 필요충분 조건입니다. 만약 R의 아이디얼 A와 B가 서로소이면, AB = A∩B입니다; 게다가, 만약 C가 A가 BC를 포함함을 만족하는 세 번째 아이디얼이면, A는 C를 포함합니다. 중국 나머지 정리(Chinese remainder theorem)는 서로소 아이디얼을 사용하여 임의의 교환 링으로 일반화될 수 있습니다.

Probability of coprimality

둘의 무작위로 선택된 정수 a와 b가 주어지면, a와 b가 서로소일 가능성이 얼마나 되는지 묻는 것이 합리적입니다. 이 결정에서, a와 b가 서로소인 것과 소수가 그것들 둘 다를 나누는 것은 필요충분 조건이라는 특성을 사용하는 것이 편리합니다 (산술의 기본 정리(Fundamental theorem of arithmetic)를 참조하십시오).

비공식적으로, 임의의 숫자가 소수 (또는 실제로 임의의 정수)로 나뉠 수 있는 확률 $p$ 는 $1/p$ 입니다; 예를 들어, 모든 각 7번째 정수는 7로 나뉠 수 있습니다. 따라서 두 숫자가 둘 다 p로 나뉠 확률은 $1/p^{2}$ 이고, 그것들 중 적어도 하나가 그렇지 않을 확률은 $1-1/p^{2}$ 입니다. 구별되는 소수와 결합된 임의의 유한 나눔가능성 사건의 모음은 서로 독립적입니다. 예를 들어, 두 사건의 경우에서, 숫자는 소수 p와 q로 나뉠 수 있는 것과 그것이 pq로 나뉠 수 있는 것은 필요충분 조건입니다; 후자의 사건은 확률 1/pq을 가집니다. 만약 그러한 추론이 무한하게 많은 나눔가능성 사건으로 확장될 수 있다는 발견적 가정을 하면, 두 숫자가 서로소일 확률이 모든 소수에 걸쳐 곱에 의해 주어질 것이라는 추측으로 이어집니다:

\prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.

여기서 ζ는 리만 제타 함수(Riemann zeta function)를 참조하며, 소수에 걸쳐 곱을 ζ(2)와 관련시키는 항등식은 오일러 곱(Euler product)의 예제이고, π²/6으로 ζ(2)의 평가는 1735년 레온하르트 오일러(Leonhard Euler)에 의해 해결된 바젤 문제(Basel problem)입니다. 1735년.

각 양의 정수가 같은 확률로 발생하도록 양의 정수를 무작위로 선택하는 방법은 없지만, 위와 같은 "무작위로 선택된 정수"에 대한 명제는 자연 밀도(natural density)의 개념을 사용함으로써 공식화될 수 있습니다. 각 양의 정수 N에 대해, P_N을 $\{1,2,\ldots ,N\}$ 에서 둘의 무작위로 선택된 숫자가 서로소일 확률로 놓습니다. 비록 P_N이 정확하게 $6/\pi ^{2}$ 와 같지는 않지만, 작업과 함께^[9] $N\to \infty$ 일 때 극한에서, 확률 $P_{N}$ 이 $6/\pi ^{2}$ 으로 접근함을 보일 수 있습니다.

보다 일반적으로, 서로소인 k 무작위로 선택된 정수의 확률은 $1/{\zeta (k)}$ 입니다.

Generating all coprime pairs

The order of generation of coprime pairs by this algorithm. First node (2,1) is marked red, its three children are shown in orange, third generation is yellow, and so on in the rainbow order.

양의 서로소 숫자 $(m,n)$ ( $m>n$ )의 모든 쌍은 둘의 분리된 완전한 삼항 트리(ternary tree), (짝수–홀수 및 홀수–짝수 쌍에 대해) $(2,1)$ 에서 시작하는 하나의 트리와^[10] (홀수–홀수 쌍에 대해) $(3,1)$ 에서 시작하는 다른 트리에서 배열될 수 있습니다.^[11] 각 꼭짓점 $(m,n)$ 의 자식은 다음과 같이 생성됩니다:

가지 1: $(2m-n,m)$
가지 2: $(2m+n,m)$
가지 3: $(m+2n,n)$

이 스킴은 유효하지 않은 구성원을 갖지 않는 포괄적이고 비-중복입니다.

Applications

기계 설계에서, 같은, 균등한 기어(gear) 마모는 서로 맞물리는 두 기어의 톱니 숫자를 상대적으로 소수로 선택함으로써 달성됩니다. 1:1 기어 비율이 희망될 때, 둘의 같은-크기 기어에 상대적으로 소수 기어는 그들 사이에 삽입될 수 있습니다.

컴퓨터-이전 암호화(cryptography)에서, 일부 버남 암호(Vernam cipher) 기계는 다른 길이의 여러 키 테이프의 루프를 결합했습니다. 많은 회전자 기계(rotor machine)는 톱니의 다른 숫자의 회전자를 조합합니다. 그러한 조합은 전체 길이의 집합이 쌍별 서로소일 때 가장 잘 작동합니다.^[12]^[13]^[14]^[15]

Generalizations

이 개념은 $\mathbb {Z}$ 이외의 다른 대수적 구조으로 확장될 수 있습니다; 예를 들어, 최대 공통 약수(greatest common divisor)가 1인 다항식(polynomials)은 서로소 다항식(coprime polynomials)이라고 불립니다.

Notes

^ Eaton, James S. (1872). A Treatise on Arithmetic. Boston: Thompson, Bigelow & Brown. p. 49. Retrieved 10 January 2022. Two numbers are mutually prime when no whole number but one will divide each of them
^ Hardy & Wright 2008, p. 6
^ Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics / A Foundation for Computer Science, Addison-Wesley, p. 115, ISBN 0-201-14236-8
^ Ore 1988, p. 47
^ Niven & Zuckerman 1966, p. 22, Theorem 2.3(b)
^ Niven & Zuckerman 1966, p. 6, Theorem 1.8
^ Niven & Zuckerman 1966, p.7, Theorem 1.10
^ Rosen 1992, p. 140
^ This theorem was proved by Ernesto Cesàro in 1881. For a proof, see Hardy & Wright 2008, Theorem 332
^ Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the Pythagorean triplets revisited", Mathematical Gazette, 78: 190–193, doi:10.2307/3618576.
^ Mitchell, Douglas W. (July 2001), "An alternative characterisation of all primitive Pythagorean triples", Mathematical Gazette, 85: 273–275, doi:10.2307/3622017.
^ Klaus Pommerening. "Cryptology: Key Generators with Long Periods".
^ David Mowry. "German Cipher Machines of World War II". 2014. p. 16; p. 22.
^ Dirk Rijmenants. "Origins of One-time pad".
^ Gustavus J. Simmons. "Vernam-Vigenère cipher".

References

Hardy, G.H.; Wright, E.M. (2008), An Introduction to the Theory of Numbers (6th ed.), Oxford University Press, ISBN 978-0-19-921986-5
Niven, Ivan; Zuckerman, Herbert S. (1966), An Introduction to the Theory of Numbers (2nd ed.), John Wiley & Sons
Ore, Oystein (1988) [1948], Number Theory and Its History, Dover, ISBN 978-0-486-65620-5^{[dead link]}
Rosen, Kenneth H. (1992), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0-201-57889-8