• "유클리드 알고리즘"의 개념을 소개합니다.
• 다양한 수학적 방법으로 가장 공약수를 찾는 방법을 배웁니다.

수업 중

유클리드 알고리즘의 개념

2000년이 넘은 가장 오래된 수학 중 하나입니다.

유클리드의 알고리즘은 다음을 찾기 위해 발명되었습니다. 최대 공약수정수 쌍.

최대 공약수

최대 공약수(GCD)는 나머지 없이 두 숫자를 나누는 숫자이며 이 숫자의 다른 약수로 나머지 없이 자체적으로 나눌 수 있습니다.

즉, 이것은 두 수를 나머지 없이 나눌 수 있는 최대 수이며, 이에 대한 공약수를 구합니다.

나눗셈으로 GCD를 찾는 알고리즘

나눗셈으로 최대공약수를 찾는 알고리즘 설명

큰 수를 작은 수로 나눈 값

나머지 없이 나눌 수 있는 경우 작은 수는 최대 공약수입니다. 이제 나가셔야 합니다 주기

나머지가 있으면 더 큰 수를 나눗셈의 나머지로 대체합니다.

1번 항목으로 이동합니다.

예시:

300과 180의 최대공약수를 구하세요.

300/180 = 1(나머지 120)

180/120 = 1(나머지 60)

120/60 = 2(나머지 0).

끝:최대공약수는 6이다.

V 주기"a" 또는 "b"는 나눗셈의 나머지 부분을 수정합니다. 나머지가 없을 때(“a”에 있는지 “b”에 있는지 모르므로 둘 다 확인합니다. 정황), 사이클이 종료됩니다.

마지막에 "a"와 "b"의 합이 표시됩니다. 왜냐하면 어떤 변수에 최대 공약수가 쓰여 있는지, 그리고 그 중 하나는 0이므로 결과에 영향을 주지 않기 때문입니다. 합집합.

빼기로 GCD를 찾는 알고리즘

빼기로 최대 공약수를 찾는 알고리즘에 대한 설명

큰 수에서 작은 수 빼기

0으로 밝혀지면 숫자는 서로 같고 최대 공약수입니다. 루프 출구

빼기 결과가 0이 아닌 경우 더 큰 수를 빼기 결과로 대체합니다.

1번 항목으로 이동합니다.

예시:숫자 300과 180을 찾으십시오.

끝: 300과 180의 가장 흔한 약수는 60입니다.

피타고라스 학파는 두 세그먼트의 최대 공약수를 찾는 방법(교대 뺄셈 방법)을 알고 있었습니다.

2의 최대공약수를 구할 때 세그먼트위와 같은 방법으로 진행합니다.

나머지가 있는 나누기 연산은 기하학적 대응으로 대체됩니다. 부분가능한 한 많이 더 큰 세그먼트를 위해 따로 설정하고 더 큰 세그먼트의 나머지 부분(그리고 이것이 나눗셈의 나머지 부분)은 더 작은 세그먼트로 연기됩니다.

세그먼트인 경우 ㅏ그리고 비상응하는 경우 마지막 0이 아닌 나머지는 세그먼트의 가장 큰 공통 측정값을 제공합니다.

공약 불가능성의 경우, 0이 아닌 잔기의 결과 시퀀스는 무한합니다.

예시:

선분으로 A=C = 72°, B= 36°인 이등변 삼각형 ABC의 변 AB와 AC를 취합니다.

첫 번째 나머지로 세그먼트 AD(각 C의 CD 이등분선)를 얻고, 쉽게 볼 수 있는 것처럼 나머지 시퀀스와 0은 무한대가 됩니다.

따라서 세그먼트 AB와 AC는 측정할 수 없습니다.

질문

1. 유클리드 알고리즘이란?

2. 최대공약수는?

사용된 소스 목록

1. 주제에 대한 교훈: "유클리드 알고리즘", Korchevoi P.I., Lutsk

2. A. I. Shchetnikov, 유클리드 알고리즘 및 연속 분수. - 노보시비르스크: ANT, 2003

3. Countinho S. 정수론 소개. 알고리즘 RSA, - M., 2001

4. 코스리킨 A.I. 대수학 소개, - M., 2000

선생님이 편집해서 보내주신 키예프 국립 대학교. 타라스 셰브첸코솔로비요프 MS

수업 진행 중

코르체보이 P.I.

솔로비요프 MS

현대 교육에 대한 질문을 제기하거나 아이디어를 표현하거나 긴급한 문제를 해결할 수 있습니다. 교육포럼

전자 상거래에 널리 퍼져 있습니다. 또한 이 알고리즘은 Sturm 방법에서 선형 디오판틴 방정식을 풀고 연속 분수를 구성하는 데 사용됩니다. 유클리드의 알고리즘은 4제곱합에 대한 라그랑주 정리와 산술의 기본 정리와 같은 현대 정수론의 정리를 증명하는 주요 도구입니다.

백과사전 YouTube

1 / 5

✪ 수학. 자연수: 유클리드 알고리즘. Foxford 온라인 학습 센터

✪ 유클리드 알고리즘

✪ 유클리드 알고리즘, GCD를 찾는 빠른 방법

✪ 수학 71. 최대공약수. 유클리드 알고리즘 - Academy of Entertaining Sciences

✪ 20 while 루프 유클리드 Python 알고리즘

자막

이야기

고대 그리스 수학자들은 이 알고리즘을 ἀνθυφαίρεσις 또는 ἀνταναίρεσις - "상호 빼기". 이 알고리즘은 Euclid에 의해 발견되지 않았습니다. 토피카아리스토텔레스. 유클리드의 "원소"에서는 두 가지 자연수의 최대 공약수를 찾는 책 VII와 두 동질 양의 최대 공약수를 찾는 책 X에 대해 두 번 설명합니다. 두 경우 모두 두 세그먼트의 "공통 측정값"을 찾기 위해 알고리즘에 대한 기하학적 설명이 제공됩니다.

설명

정수에 대한 유클리드 알고리즘

허락하다 a (\displaystyle a)그리고 b(\디스플레이스타일 b)- 동시에 0이 아닌 정수 및 일련의 숫자

각각의 사실에 의해 결정 r k (\디스플레이 스타일 r_(k))- 이것은 이전 숫자를 이전 숫자로 나눈 나머지이며, 끝에서 두 번째 숫자는 마지막 숫자로 나눕니다. 즉,

그런 다음 gcd( ㅏ, 비), 최대공약수 ㅏ그리고 비, 와 동등하다 아르 자형 n , 이 시퀀스의 0이 아닌 마지막 멤버.

존재그런 아르 자형 1 , 아르 자형 2 , ..., 아르 자형 n , 즉 나머지로 나눗셈의 가능성 중에 N어떤 전체를 위해 중그리고 전체 N≠ 0은 귀납법으로 증명 중.

단정이 알고리즘은 다음 두 명령문을 따릅니다.

• 허락하다 ㅏ = 비⋅큐 + 아르 자형, gcd(a, b) = gcd(b, r).

증거

• GCD( 아르 자형, 0) = 아르 자형 0이 아닌 경우 아르 자형(0은 0이 아닌 다른 정수로 나눌 수 있기 때문입니다).

유클리드의 기하학적 알고리즘

길이의 두 부분이 주어질 때 ㅏ그리고 비. 더 큰 세그먼트에서 더 작은 세그먼트를 빼고 더 큰 세그먼트를 결과 차이로 바꿉니다. 세그먼트가 같아질 때까지 이 작업을 반복합니다. 이런 일이 발생하면 원래 세그먼트를 측정할 수 있고 마지막으로 얻은 세그먼트가 가장 큰 공통 측정값이 됩니다. 공통 측정이 없으면 프로세스가 무한합니다. 이 형식에서 알고리즘은 Euclid에 의해 설명되고 나침반과 눈금자를 사용하여 구현됩니다.

예시

설명을 위해 Euclid 알고리즘이 gcd를 찾는 데 사용됩니다. ㅏ= 1071 및 비= 462. 우선 1071에서 462의 배수를 빼면 차이가 462보다 작습니다. 462를 두 번 빼야 합니다( 큐 0 = 2), 나머지 147:

1071 = 2 × 462 + 147.

그런 다음 147보다 작은 차이가 나올 때까지 462에서 147의 배수를 뺍니다. 147을 세 번 빼야 합니다( 큐 1 = 3), 나머지 21:

462 = 3 x 147 + 21.

그런 다음 21보다 작은 차이가 나올 때까지 147에서 21의 배수를 뺍니다. 21을 7번 빼야 합니다( 큐 2 = 7), 나머지 없이 남아 있음:

147 = 7 x 21 + 0.

따라서 시퀀스 > b > 아르 자형 1 > 아르 자형 2 > 아르 자형 3 > … > 아르 자형이 특별한 경우 n은 다음과 같습니다.

1071 > 462 > 147 > 21.

마지막 나머지가 0이므로 알고리즘은 21로 끝나고 gcd(1071, 462) = 21로 끝납니다.

표 형식의 단계는 다음과 같습니다.

애플리케이션

확장된 Euclid 알고리즘과 Bezout의 관계

수식 r i (\displaystyle r_(i))다음과 같이 다시 작성할 수 있습니다.

여기 에스그리고 티전체. 최대 공약수 의 이러한 표현을 Bezout 관계라고 하며, 숫자는 에스그리고 티- 계수 베주 . Bezout의 관계는 유클리드의 보조정리 및 산술의 주요 정리 증명의 핵심입니다.

연속 분수

유클리드의 알고리즘은 연속 분수와 매우 밀접하게 관련되어 있습니다. 태도 ㅏ/비연속 분수 표현을 허용합니다.

이 경우 마지막 항이 없는 연속 분수는 Bezout 계수의 비율과 같습니다. 티/에스빼기 기호로 촬영:

유클리드 알고리즘을 정의하는 등식 시퀀스는 다음 형식으로 다시 작성할 수 있습니다.

방정식의 우변의 마지막 항은 항상 다음 방정식의 좌변의 역수와 같습니다. 따라서 처음 두 방정식은 다음과 같은 형식으로 결합될 수 있습니다.

세 번째 평등은 표현식의 분모를 대체하는 데 사용할 수 있습니다. 아르 자형 1 /아르 자형 0 , 우리는 다음을 얻습니다:

마지막 잔류 비율 아르 자형 케이 /아르 자형 케이−1은 항상 시퀀스의 다음 등식을 사용하여 대체될 수 있으며, 마지막 방정식까지 계속됩니다. 결과는 연속 분수입니다.

다항식에 대한 일반화된 유클리드 알고리즘

유클리드 알고리즘과 확장된 유클리드 알고리즘은 자연스럽게 다항식의 고리로 일반화됩니다. 케이[엑스] 임의의 필드에 대한 하나의 변수에서 케이, 이러한 다항식의 경우 나머지가 있는 나누기 연산이 정의되어 있기 때문입니다. Euclid의 다항식 알고리즘을 실행할 때 정수에 대한 Euclid의 알고리즘과 유사하게 PRS(다항식 나머지)의 시퀀스를 얻습니다.

링 예 지[엑스]

정의에 의해 cont(f)를 Z[x]로부터의 다항식 f(x)의 계수의 gcd라고 하자 - 콘텐츠다항식. f(x)를 cont(f)로 나눈 몫은 원시 부분다항식 f(x)이며 primpart(f(x))로 표시됩니다. 이러한 정의는 두 다항식의 gcd를 찾는 데 필요합니다. 페이지 1(x)그리고 페이지 2(x)링 Z[x]에서. 정수에 대한 다항식의 경우 다음이 참입니다.

계속해서 ((\displaystyle 계속() NODNOD ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x)),cont(p_(2)(x))\),)

P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=) GCD ( p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ) . (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\).)

따라서 두 개의 임의 다항식의 gcd를 찾는 문제는 원시 다항식의 gcd를 찾는 문제로 축소됩니다.

Z[x]에서 두 개의 원시 다항식 p 1 (x) 및 p 2 (x)가 있다고 하자. ) = n, m > n. 나머지가 있는 다항식의 나눗셈은 가장 높은 피제수 계수를 가장 높은 제수 계수로 정확히 나눌 수 있음을 의미하며, 일반적으로 나머지로 나눗셈을 수행할 수 없습니다. 따라서 의사 나눗셈 알고리즘이 도입되었지만 그럼에도 불구하고 의사 몫과 의사 나머지(prem)를 얻을 수 있으며, 이 알고리즘은 그 자체가 정수에 대한 다항식 집합에 속합니다.

의사 나눗셈은 나눗셈 자체가 다항식의 곱셈에 의해 선행된다는 것을 의미합니다. p 1 (x) (\displaystyle p_(1)(x))에 (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), 그건

L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg ⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

어디 q (x) (\displaystyle q(x))그리고 r (x) (\displaystyle r(x))- 각각 pseudopartial 및 pseudoresidue.

그래서, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), 게다가 deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). 그런 다음 유클리드 알고리즘은 다음 단계로 구성됩니다.

1. GCD 내용 계산:

C:= (\디스플레이 스타일 c:=) GCD ( co n t (p 1) , co n t (p 2) ) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).

2. 기본 부품 계산:

P 1 '(x) := p r i m p a r t (p 1 (x)) ; (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)

P 2 '(x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)

3. 다항식 잔기의 시퀀스 구축:

P 1 ' (x) , (\displaystyle p_(1)"(x),)

P 2 ′ (x) , (\displaystyle p_(2)"(x),)

P 3 (x) := prem (p 1 ' (x) , p 2 ' (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2) )"(엑스)))

P 4 (x) := prem (p 2 ′(x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (엑스)))

P 5 (x) := prem (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x) ))))

. . . (\디스플레이 스타일 ...)

P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)

유클리드 알고리즘정수 쌍의 최대 공약수(gcd)를 찾는 알고리즘입니다.

최대공약수(GCD)나머지 없이 두 숫자를 나누는 숫자이고 주어진 두 숫자의 다른 약수로 나머지 없이 자체적으로 나눌 수 있는 숫자입니다. 간단히 말해서, 이것은 gcd를 구하는 두 숫자를 나머지 없이 나눌 수 있는 가장 큰 숫자입니다.

나눗셈으로 GCD를 찾는 알고리즘

1. 큰 수를 작은 수로 나눕니다.
2. 나머지 없이 나누면 더 작은 숫자가 GCD입니다(루프를 종료해야 함).
3. 나머지가 있으면 더 큰 숫자가 나눗셈의 나머지로 대체됩니다.
4. 1번 항목으로 넘어갑시다.

예시:
30 및 18에 대한 GCD를 찾으십시오.
30 / 18 = 1(나머지 12)
18 / 12 = 1(나머지 6)
12 / 6 = 2(나머지 0)
끝: GCD는 6의 약수입니다.
gcd(30, 18) = 6

a = 50 b = 130 동안 a != 0 및 b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

루프에서 나눗셈의 나머지는 변수 a 또는 b에 기록됩니다. 변수 중 하나 이상이 0이면 루프가 종료됩니다. 이것은 다른 하나가 GCD를 포함한다는 것을 의미합니다. 그러나 우리는 어느 쪽인지 모릅니다. 따라서 GCD의 경우 이러한 변수의 합을 찾습니다. 변수 중 하나가 0이므로 결과에 영향을 주지 않습니다.

빼기로 GCD를 찾는 알고리즘

1. 큰 수에서 작은 수를 뺍니다.
2. 0으로 나오면 숫자가 서로 같고 GCD임을 의미합니다(루프를 종료해야 함).
3. 빼기 결과가 0과 같지 않으면 더 큰 숫자가 빼기 결과로 바뀝니다.
4. 1번 항목으로 넘어갑시다.

예시:
30 및 18에 대한 GCD를 찾으십시오.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
끝: GCD는 빼기 또는 감수입니다.
gcd(30, 18) = 6

a = 50 b = 130 while a != b: a > b: a = a - b else : b = b - a 인쇄(a)

1.1 유클리드 알고리즘의 적용

모든 좋은 작업과 마찬가지로 Euclid의 알고리즘은 원래 예상했던 것보다 훨씬 더 많은 작업을 수행합니다. 이를 보면, 예를 들어 제수 a와 b의 집합이 제수 집합(a, b)과 일치한다는 것이 분명합니다. 또한 Z에서(또는 원하는 경우 포인트 2의 정리에서) 숫자 u와 v를 찾는 실용적인 방법을 제공합니다.

rn = au + bv = (a, b).

실제로 평등의 사슬에서 우리는 다음을 가지고 있습니다.

r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...

(우리는 아래에서 위로 등식의 사슬을 따라 이동하여 각 다음 등식의 나머지를 표현하고 이 순간까지 이미 얻은 표현으로 대체합니다)

금 + bv = (a, b).

의심할 여지 없이, 유클리드가 숫자와 관련하여 두 양의 공약수(그리고 두 자연수의 공약수는 분명히 최대공약수)를 결정하기 위해 설명한 절차는 유클리드보다 오래 전에 발명되었습니다. 같은 방식으로 GCD는 고대 중국 수학자에 의해 발견되었습니다. 그리고 이 절차가 "초기"부터 정확히 르네상스 시대에 알려지게 되었다는 사실만으로도 "유클리드 알고리즘"이라는 이름이 붙었습니다.

아마도 고대 상인들이 정수의 다양한 비율을 비교해야 했던 상업 관행에서 비롯된 것 같습니다. 예를 들어, 숫자 3703700과 1234567과 숫자 22962965와 7654321의 비율을 어떻게 비교합니까? 더 작은 숫자가 더 큰 숫자에 몇 배나 들어갈 수 있는지 알아내려고 하는 것은 아주 자연스러운 일이었습니다. 이제 3703700 = 2 1234567 + 1234566 및 22962965 = 3 7654321 + 2임을 쉽게 확인할 수 있습니다. 이제 3703700 대 1234567의 비율이 2329666의 비율보다 작은 것이 분명합니다.

2,99999919 <= 3, 000000261,

긴 문구로 설명된 고대 계산기.

예를 들어 더 가까운 숫자의 비율을 비교해야 하는 경우 계산이 더 복잡해집니다.

71755875 = 61735500 + 10020375;

61735500 = 6 10020375 + 1613250;

10020375 = 6 1613250 + 340875;

1613250 = 4 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 91125 + 67500;

91125 = 67500 + 23625;

67500 = 2 23625 + 20250;

23625 = 20250 + 3375;

20250 = 6 3375.

유클리드의 알고리즘을 사용하면 71755875 및 61735500의 GCD를 결정할 수 있으며, 이는 3375와 동일하며 71755875에서 61735500까지의 비율을 연속 분수로 확장하는 것에 해당합니다.

유클리드의 알고리즘은 숫자를 연속 분수로 분해하는 현대적인 절차와 동일한 것으로 밝혀졌으며 또한 숫자의 비율을 "반올림"할 수 있습니다. 분모가 큰 분수를 분모가 작은 분수와 매우 가까운 분수로 바꿉니다. 과연 그 표현은

분수와 같음 현대 수학에서 관계 b \u003d를 연속 (또는 연속) 분수로 확장하는 "접근 분수"라고합니다.

그것은 분명하다

b=1+< 1 + и б=1 + > 1+ = ,

하는 한

위의 비교 >는 III 세기에 이루어졌습니다. 기원전. 논문 "달과 태양의 거리와 크기"에서 Samos의 Aristarchus.

어떤 (합리적 또는 무리수) 숫자의 연속 분수로의 확장의 수렴이 이 숫자의 가장 합리적인 근사치라는 것이 이제 알려져 있습니다.

다항식 알고리즘

유클리드 알고리즘은 한 변수에서 두 개의 정수와 두 개의 다항식의 최대공약수를 찾는 방법입니다.

가장 오래된 수학적 알고리즘 중 하나는 두 양수의 최대 공약수를 찾는 유클리드 알고리즘입니다. 다음은 가장 간단한 형태입니다. 두 개의 정수가 주어집니다. 그들이 동등하다면 ...

유클리드 고리의 유클리드 알고리즘 분석

유클리드 알고리즘의 분석을 진행하기 전에 피보나치 수를 고려하십시오. 피보나치 수열의 본질은 1.1에서 시작하여 이전 두 수를 더하여 다음 수를 얻는다는 것입니다. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 .....

"알고리즘" 개념 형성의 역사. 수학의 역사에서 유명한 알고리즘

유클리드의 알고리즘은 두 양의 정수의 최대공약수를 계산할 수 있는 보편적인 방법입니다. 나누기로 GCD를 찾는 알고리즘 설명: 1. 큰 수를 작은 수로 나눕니다. 2. 나머지 없이 나누면 ...

가우스 정수의 고리

우리는 고리에 대한 최대 공약수의 일반적인 정의를 사용합니다. 두 가우스 수의 gcd는 다른 공약수로 나눌 수 있는 공약수입니다. 정수 집합과 마찬가지로 ...

잔여 클래스 시스템의 수학적 기초

예를 들어 보십시오. p = 6이라고 하자. 그런 다음 모듈로 6의 정수 집합에 대한 6개의 파티션 클래스가 있습니다. r = 0; r = 1; r = 2; r=3; r=4; r=5; 여기서 r은 정수를 6으로 나눈 나머지를 나타냅니다...

중등학교 상급반의 선택수업에서 다항식을 공부하는 방법

다항식의 고리가 끝나게하십시오. 정의 1: 다항식이 있는 경우 나눗셈의 나머지가 0인 경우 이를 다항식의 제수라고 하며 다음과 같이 표시합니다. ()...

현대 수학의 형성과 구조의 주요 단계

기원전 3세기에 알렉산드리아에 "시작"의 러시아어 번역으로 같은 이름의 유클리드 책이 나타났습니다. 라틴어 이름 "Beginnings"에서 "초기하학"이라는 용어가 나왔습니다. 에도 불구하고...

어떤 도시 N의 영토에는 이 공장의 제품을 공급하는 공장과 상점이 있습니다. 개발의 결과 통신을 배치할 수 있는 경로를 식별하고 각 경로에 대한 생성 비용을 추정했습니다 ...

경제학에서 이산 수학 방법의 적용

부패하기 쉬운 상품을 운송하는 회사는 Suifenhe에서 Khabarovsk까지 상품을 배송해야 하며 배송할 수 있는 여러 경로가 있습니다. Suifenhe와 City 2 사이의 거리는 15km입니다...

"공간" 개념과 비유클리드 기하학의 발전

합리적인 표현을 통합하는 특별한 방법

다항식 및의 gcd를 찾는 것이 필요합니다. 일반성을 잃지 않고 차수가 차수보다 높지 않다고 가정합니다. 우리는 다항식을 다음 형식으로 나타냅니다. 여기서 나눗셈의 나머지는 입니다. 그러면 차수가 제수의 차수보다 작습니다. 더 나아가...

잔류 이론

잔류 이론

정의. 숫자 a, b, c, ..., k ??Z를 동시에 나누는 숫자 d??Z를 이 숫자의 공약수라고 합니다. 이 속성을 가진 가장 큰 d를 최대 공약수라고 합니다. 표기법: d = (a , b , c , ..., k) . 정리. (a , b) = d...

잔류 이론

선형 디오판틴 방정식을 풀기 위해 필요하다고 합시다. ax + by = c , 여기서 a , b , c ??Z ; 및 b는 0이 아닙니다. 이 방정식을 보면서 추론해 봅시다. (a , b) = d 라고 합시다. 그러면 a = a 1 d ; b = b 1 d이고 방정식은 다음과 같습니다. a 1 d x + b 1 d y = c , 즉 d(a 1 x + b 1 y) = c...

유클리드 알고리즘 사용과 인수분해라는 두 가지 주요 방법으로 GCD를 찾는 두 가지 주요 방법을 고려해 보겠습니다. 2개, 3개 및 그 이상의 숫자에 두 가지 방법을 모두 적용해 보겠습니다.

GCD를 찾는 유클리드 알고리즘

유클리드 알고리즘을 사용하면 두 양수의 최대 공약수를 쉽게 계산할 수 있습니다. 우리는 최대 공약수: 행렬식, 예 섹션에서 유클리드 알고리즘의 공식과 증명을 제공했습니다.

알고리즘의 본질은 다음과 같은 형식의 일련의 평등을 얻는 동안 나머지로 일관되게 나눗셈을 수행하는 것입니다.

a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

나눗셈을 마칠 수 있을 때 rk + 1 = 0, 여기서 r k = gcd (a, b).

실시예 1

64 그리고 48 .

해결책

a = 64 , b = 48 이라는 표기법을 소개하겠습니다.

Euclid 알고리즘을 기반으로 나누기를 수행합니다. 64 에 48 .

우리는 1과 나머지 16을 얻습니다. q 1 = 1, r 1 = 16인 것으로 나타났습니다.

두 번째 단계는 분할 48 16까지, 우리는 3을 얻습니다. 그건 q2 = 3, ㅏ r 2 = 0 .따라서 숫자 16은 조건의 숫자에 대한 최대 공약수입니다.

대답: gcd(64, 48) = 16.

실시예 2

숫자의 GCD는 무엇입니까 111 그리고 432 ?

해결책

나누다 432 에 111 . Euclid의 알고리즘에 따르면 등식 사슬은 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 입니다.

따라서 숫자의 최대공약수는 111 그리고 432 3 입니다.

대답: gcd(111, 432) = 3.

실시예 3

661 과 113 의 최대공약수를 구하세요.

해결책

숫자를 순차적으로 나누어 GCD를 얻습니다. (661 , 113) = 1 . 이것은 661과 113이 상대적으로 소수임을 의미합니다. 우리는 소수의 표를 보면 계산을 시작하기 전에 이것을 알아낼 수 있습니다.

대답: gcd(661, 113) = 1.

숫자를 소인수로 분해하여 GCD 찾기

두 수의 최대공약수를 인수분해로 구하려면 이 두 수를 분해하여 얻은 소인수와 공약수를 모두 곱해야 합니다.

실시예 4

숫자 220과 600을 소인수로 분해하면 두 가지 제품이 나옵니다. 220 = 2 2 5 11그리고 600 = 2 2 2 3 5 5. 이 두 제품의 공통 요소는 2, 2 및 5입니다. 이것은 NOD를 의미합니다 (220, 600) = 2 2 5 = 20.

실시예 5

숫자의 최대공약수 구하기 72 그리고 96 .

해결책

숫자의 모든 소인수 찾기 72 그리고 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

두 숫자에 대한 공통 소인수: 2 , 2 , 2 및 3 . 이것은 NOD를 의미합니다 (72, 96) = 2 2 2 3 = 24.

대답: gcd(72, 96) = 24.

두 숫자의 최대 공약수를 찾는 규칙은 최대 공약수의 속성을 기반으로 하며, 이에 따라 gcd (ma 1 , mb 1) = m gcd (a 1 , b 1) , 여기서 m은 임의의 양의 정수입니다. .

세 개 이상의 숫자의 GCD 찾기

GCD를 찾아야 하는 숫자의 수에 관계없이 연속으로 두 숫자의 GCD를 찾는 동일한 알고리즘을 따릅니다. 이 알고리즘은 다음 정리의 적용을 기반으로 합니다. 여러 숫자의 GCD a 1 , a 2 , … , k숫자와 같습니다 닥, 이는 gcd의 순차 계산에서 찾을 수 있습니다. (a 1 , a 2) = d 2, GCD(d 2 , a 3) = d 3 , GCD(d 3 , a 4) = d 4 , … , GCD(d k - 1 , a k) = d k .

실시예 6

4개의 숫자 78, 294, 570의 최대공약수를 구합니다. 36 .

해결책

표기법을 소개하겠습니다: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

숫자 78과 294의 GCD를 찾는 것부터 시작하겠습니다. d2= GCD (78 , 294) = 6 .

이제 d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) 를 찾기 시작하겠습니다. 유클리드 알고리즘에 따르면 570 = 6 95 .그 의미 d 3 = GCD (6 , 570) = 6 .

찾기 d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 나머지 없이 6으로 나누어집니다. 이것은 우리가 얻을 수 있습니다 d4= GCD (6 , 36) = 6 .

d4 = 6, 즉, GCD (78 , 294 , 570 , 36) = 6 .

대답:

이제 이러한 숫자와 더 많은 숫자에 대해 GCD를 계산하는 다른 방법을 살펴보겠습니다. 숫자의 모든 공통 소인수를 곱하여 gcd를 찾을 수 있습니다.

실시예 7

숫자 78, 294, 570의 gcd를 계산하고 36 .

해결책

이 숫자를 소인수로 분해해 보겠습니다. 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

네 숫자 모두에 대해 공통 소인수는 숫자 2와 3입니다.

NOD (78, 294, 570, 36) = 2 3 = 6.

대답: gcd(78, 294, 570, 36) = 6 .

음수의 gcd 찾기

음수를 처리해야 하는 경우 이 숫자의 모듈을 사용하여 최대 공약수를 찾을 수 있습니다. 반대 부호가 있는 숫자의 속성을 알고 있으면 이 작업을 수행할 수 있습니다. 숫자 N그리고 -N같은 약수를 가집니다.

실시예 8

음의 정수의 gcd 찾기 − 231 그리고 − 140 .

해결책

계산을 수행하기 위해 조건에 ​​주어진 숫자의 모듈을 취합시다. 이것은 숫자 231과 140이 될 것입니다. 간단히 말해보자: GCD (− 231 , − 140) = GCD(231, 140) . 이제 두 숫자의 소인수를 찾기 위해 유클리드 알고리즘을 적용해 보겠습니다. 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 및 42 = 7 6. 우리는 gcd (231, 140) = 7을 얻습니다. .

그리고 NOD 이후로 (− 231 , − 140) = GCD (231 , 140) , 숫자의 gcd − 231 그리고 − 140 같음 7 .

대답: gcd (− 231 , − 140) = 7 .

실시예 9

세 숫자의 gcd 결정 - 585, 81 및 − 189 .

해결책

위 목록의 음수를 절대 값으로 바꾸면 GCD를 얻습니다. (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . 그런 다음 주어진 모든 숫자를 소인수로 분해합니다. 585 = 3 3 5 13, 81 = 3 3 3 3 및 189 = 3 3 3 7. 소인수 3과 3은 세 수에 공통입니다. GCD (585 , 81 , 189) = GCD (- 585 , 81 , - 189) = 9 입니다.

대답: GCD(− 585 , 81 , − 189) = 9 .

텍스트에서 실수를 발견하면 강조 표시하고 Ctrl+Enter를 누르십시오.