고대 이집트 곱셈법 문서 원본 보기

{{위키데이터 속성 추적}}
'''고대 이집트 곱셈법'''은 [[구구단]]을 사용하지 않고 2로 나누고 곱하는 것과 [[덧셈]]만을 가지고 두 수를 곱하는 방법이다.
'''이집트 곱셈법'''과 '''농부 곱셈법'''은 첫 번째 수를 [[2의 거듭제곱]]들의 합으로 분해하고, 두 번째 수의 2의 거듭제곱에 대한 표를 만들어 첫 번째 수와 두 번째 수의 곱을 구한다. 어떤 지역에서는 이 방법을 아직도 사용한다.

두 번째 이집트 곱셈법과 나눗셈법은 모스크바 신관 문자와 기원전 17세기에 쓰여진 [[린드 파피루스]]에서 발견되었다.


이집트인들은 [[이진법]]을 통하여 수를 2의 거듭제곱들의 합으로 분해하지 않았다. 이집트인들은 그러한 개념을 몰랐고, 보다 간단한 방법에 의존해야 했다. 고대 이집트인들은 커다란 2의 거듭제곱수들을 계산해 놓은 표를 가지고 있었고, 그래서 매번 그 수들을 다시 계산할 필요가 없었다. 그러므로 수의 분해는 그 수를 만드는 2의 거듭제곱수들을 찾는 일로 이루어졌다. 이집트인들은 경험적으로 주어진 2의 거듭제곱의 합들은 오로지 한 가지 수로만 나타난다는 것을 알았다. 그들은 주어진 수보다 작거나 같은 수들 중에서 가장 큰 2의 거듭제곱을 찾고, 그것을 빼어나가는 것을 반복함으로써 주어진 수를 2의 거듭제곱의 합으로 분해하였다.

가장 큰 2의 거듭제곱을 찾기 위해 1에서부터 시작해 2를 계속 곱해나간다.

예:<br />
<br />
1 x 2 = 2<br />
2 x 2 = 4<br />
4 x 2 = 8<br />
8 x 2 = 16<br />
16 x 2 = 32 <br />

25를 2의 거듭제곱들의 합으로 분해하는 예:
* 25보다 작거나 같은 가장 큰 2의 거듭제곱은 16이므로,
* 25 - 16 = 9,
* 9보다 작거나 같은 가장 큰 2의 거듭제곱은 8이므로,
* 9 - 8 = 1,
* 1보다 작거나 같은 가장 큰 2의 거듭제곱은 1이므로,
* 1 - 1 = 0

그러므로 25는 16과 8, 1의 합으로 이루어진다.

== 표 ==
첫 번째 수를 분해한 뒤에, 두 번째 수에 2의 거듭제곱을 곱한 수들의 표를 만드는 것이 필요하다.

예를 들어 첫 번째 수를 분해했을 때 나오는 가장 큰 2의 거듭제곱이 16이고, 두 번째 수는 7이라하면 다음과 같은 표가 만들어질 것이다. 1; 7 2; 14 4; 28 8; 56 16; 112


첫 번째 수를 분해했을 때 나온 수들과 대응하는 두 번째 단의 수들을 더해서 결과를 얻는다.
예를 들어 25 곱하기 7을 계산하고 싶다면 25를 분해했을 때 나오는 16, 8, 1과 위의 표에서 대응하는 112, 56, 7를 모두 더하면 된다.
* 25 x 7 = 112 + 56 + 7 = 175
이 방법의 장점은 2로 곱하는 것과 덧셈, 뺄셈만을 통해 곱하기를 할 수 있다는 것이다.


예: 27 곱하기 82

:{| class="wikitable" style="text-align:right"
|-----
| | A 단 || | B 단
| | 더할 숫자&nbsp;
|-----
| | 27&nbsp; || | 82&nbsp;
| | 82&nbsp;
|-----
| | 13&nbsp; || | 164&nbsp;
| | 164&nbsp;
|-----
| | 6&nbsp; || | 328&nbsp;
| |
|-----
| | 3&nbsp; || | 656&nbsp;
| | 656&nbsp;
|-----
| | 1&nbsp; || | 1312&nbsp;
| | 1312&nbsp;
|-----
| |||| '''결과:&nbsp;2214'''&nbsp;
|}

이 방법은 곱셈의 [[분배법칙]]때문에 성립한다.
{|
|-
|<math>82 \times 27\,</math>
|<math>= 82 \times (1\times 2^0 + 1\times 2^1 + 0\times 2^2 + 1\times 2^3 + 1\times 2^4\,)</math>
|-
|
|<math>= 82 \times (1 + 2 + 8 + 16)\,</math>
|-
|
|<math>= 82 + 164 + 656 + 1312\,</math>
|-
|
|<math>= 2214\,.</math>
|}

=== 증명 ===
농부 곱셈법은 [[수학적 귀납법]]을 통해 증명할 수 있다.

자연수 n, m에 대해 PM(n, m)이 농부곱셈법의 결과를 나타낸다고 하자.

;기본적인 경우:
:<math>n = 1</math>이고 <math>m \in \N</math>인 n, m에 대해, <math>PM(n, m) = PM(1, m) = 1 \cdot m = n \cdot m</math>은 참이다.

:<math>n = 2</math>이고 <math>m \in \N</math>인 n, m에 대해, <math>PM(n, m) = PM(2, m) = 2 \cdot m = n \cdot m</math>은 참이다.

;일반적인 경우:
:<math>PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right ) = n \cdot m</math>이라고 가정하면,
:<math>n\!\,</math>이 짝수일 때, <math>PM(n, m) = PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right )</math>이 성립한다.
:<math>n\!\,</math>이 홀수일 때, <math>PM(n, m) = PM \left (\left \lfloor \frac n 2 \right \rfloor, 2m \right ) + m</math>이 성립한다.
:따라서 모든 자연수 n, m에 대해 <math>PM(n, m) = n \cdot m</math>이 참이다.

== 같이 보기 ==
* [[이집트 수학]]
* [[곱셈 알고리즘]]
* [[이진법]]

== 외부 링크 ==
* [http://mathforum.org/dr.math/faq/faq.peasant.html 러시아 농부 곱셈법]
* [http://www.lafstern.org/matt/col3.pdf 러시아 농부 곱셈법 (pdf 파일)]

{{수론 알고리즘}}

{{전거 통제}}

[[분류:곱셈]]
[[분류:수론 알고리즘]]
[[분류:이집트 수학]]