이산수학(Discrete Mathematics)  정수와 나눗셈 (The Integers and Division) 2014년 봄학기 강원대학교 컴퓨터과학전공 문양세

These form the basics of number theory. (정수론의 기초..) Introduction The Integers and Division Of course you already know what the integers are, and what division is… (정수와 나누기… 다 아는거~) But: There are some specific notations, terminology, and theorems associated with these concepts which you may not know. (몇 가지 주요 표기, 용어, 정리 등을 배웁시다.) These form the basics of number theory. (정수론의 기초..) Vital in many important algorithms today (hash functions, cryptography, digital signatures).

Divides, Factor, and Multiple The Integers and Division Let a,bZ with a0. a|b  “a divides b” : “cZ: b=ac” “There is an integer c such that c times a equals b.” (b가 a로 나누어짐(a로 b를 나눌 수 있음)을 의미하며, 이때 몫이 c이다.) Example: 312  True, but 37  False. If a divides b, then we say a is a factor or a divisor of b, and b is a multiple of a. “b is even” :≡ 2b. Is 0 even? Is −4? 인수 배수

2. (a|b  a|c)  a | (b + c) (2|4  2|6  2|10) Some Facts of Division The Integers and Division a,b,c  Z: 1. a|0 (2|0, 3|0, …) 2. (a|b  a|c)  a | (b + c) (2|4  2|6  2|10) 3. a|b  a|bc (2|4  2|4∙3) 4. (a|b  b|c)  a|c (2|4  4|8  2|8) Proof of (2): a|b means there is an s such that b=as, and a|c means that there is a t such that c=at, so b+c = as+at = a(s+t), so a|(b+c) also.□

More Detailed Version of Proof The Integers and Division Show a,b,c  Z: (a|b  a|c)  a | (b + c). Let a, b, c be any integers such that a|b and a|c, and show that a | (b + c). By definition of |, we know s: b=as, and t: c=at. Let s, t, be such integers. Then b+c = as + at = a(s+t) so u: b+c=au, namely u=s+t. Thus a|(b+c).

Prime Numbers (소수) The Integers and Division An integer p>1 is prime iff it is not the product of any two integers greater than 1: p>1  a,bN: a>1, b>1, ab=p. The only positive factors of a prime p are 1 and p itself. Some primes: 2,3,5,7,11,13... (양의 인수(divisor)가 1과 자기 자신뿐이면 소수(prime)라 한다.) Non-prime integers greater than 1 are called composite, because they can be composed by multiplying two integers greater than 1. 합성수

Fundamental Theorem of Arithmetic (산술의 기본 정리) The Integers and Division Every positive integer has a unique representation as the product of a non-decreasing series of zero or more primes. (모든 양의 정수는 오름차순으로 정렬된 소수들의 곱으로 유일하게 표현된다. 결국 Prime Factorization(소인수분해)를 이야기한다고 볼 수 있다.) 1 = (product of empty series) = 1 2 = 2 (product of series with one element 2) 4 = 2·2 (product of series 2,2) 2000 = 2·2·2·2·5·5·5 = 24·53; 2001 = 3·23·29; 2002 = 2·7·11·13; 2003 = 2003

소수의 개수? “무한히 많은 소수가 존재함”을 증명하라. 1. 유한 개의 소수 p1, p2, …, pn이 있다고 가정하자. The Integers and Division “무한히 많은 소수가 존재함”을 증명하라. 1. 유한 개의 소수 p1, p2, …, pn이 있다고 가정하자. 2. Q = p1·p2·…·pn + 1이라 하자. 3. “산술의 기본 정리”에 의하여 Q는 소수들의 곱으로 표현된다. 4. 따라서, pj | Q(1  j  n)를 만족하는 소수 pj가 존재한다. 5. 그러면, 다음과 같은 전개가 이루어진다. 5.1 (pj | p1·p2·…·pn)  (pj |-(p1·p2·…·pn)) [a|b  a|bc] 5.2 (pj | Q) = (pj | (p1·p2·…·pn + 1)) [by step 4] 5.3 (pj | 1)? [(a|b  a|c)  a | (b + c)] 6. pj는1을 나눌 수 없으므로, 결국 가정(유한 개의 소수가 있다)이 잘못된 것이다. 즉, 소수의 개수는 무한하다. □

The Division “Algorithm” The Integers and Division Really just a theorem, not an algorithm… The name is used here for historical reasons. For any integer dividend a and divisor d≠0, there is a unique integer quotient q and remainder rN such that a = dq + r and 0  r < |d|. dividend = “피제수”, divisor = “제수” quotient = “몫”, remainder = “나머지” a,dZ, d>0: !q,rZ: 0r<|d|, a=dq+r. (! means “unique”) We can find q and r by: q=ad, r=aqd. (e.g., if a = 14 and d = 3, then q = 143 = 4 and r = 14 - 3·4 = 2.

Greatest Common Divisor (최대공약수) The Integers and Division The greatest common divisor gcd(a,b) of integers a,b (not both 0) is the largest (most positive) integer d that is a divisor both of a and of b. (최대공약수는 두 수의 공약수 중에서 가장 큰 공약수이다.) d = gcd(a,b) = max(d: d|a  d|b) Example: gcd(24,36)=? Positive common divisors: 1,2,3,4,6,12 Greatest is 12.

GCD shortcut The Integers and Division If the prime factorizations are written as and , then the GCD is given by: Example: a=84=2·2·3·7 = 22·31·71 b=96=2·2·2·2·2·3 = 25·31·70 gcd(84,96) = 22·31·70 = 2·2·3 = 12.

Relatively Primality (서로 소, 상대 소수) The Integers and Division Integers a and b are called relatively prime or coprime iff their gcd = 1. (두 수의 최대공약수가 1인 경우, 두 수는 서로 소(상대 소수)라 한다.) Example: Neither 21 and 10 are prime, but they are coprime. 21=3·7 and 10=2·5, so they have no common factors > 1, so their gcd = 1. A set of integers {a1,a2,…} is (pairwise) relatively prime if all pairs ai, aj, ij, are relatively prime. (주어진 정수들의 모든 쌍이 서로 소이면, 해당 정수들은 서로 소라 한다.) E.g., 10, 17, and 21 are relatively primes.

Least Common Multiple (최소공배수) The Integers and Division lcm(a,b) of positive integers a, b, is the smallest positive integer that is a multiple both of a and of b. m = lcm(a,b) = min(m: a|m  b|m) (최소공배수는 두 수의 공배수 중에서 가장 작은 공배수이다.) E.g. lcm(6,10)=30 If the prime factorizations are written as and , then the LCM is given by

If a and b are positive integers, then ab = gcd(a,b)·lcm(a,b) A Useful Rule The Integers and Division If a and b are positive integers, then ab = gcd(a,b)·lcm(a,b) Prove it by yourself!

An integer “division remainder” operator. Let a,dZ with d>1, then The mod Operator The Integers and Division An integer “division remainder” operator. Let a,dZ with d>1, then a mod d denotes the remainder r; i.e. the remainder when a is divided by d. r = a mod d We can compute (a mod d) by: a  d·a/d. In C programming language, “%” = mod. q

Modular Congruence (모듈로 합동?) The Integers and Division Let Z+={nZ | n>0}, the positive integers. Let a,bZ, mZ+. Then a is congruent to b modulo m, written “ab(mod m)”, iff m|(ab). Also equivalent to: (ab) mod m = 0. m으로 나누었을 때, a와 b의 나머지가 동일(합동)하다. m으로 나누어 나머지가 동일한 수의 차를 m으로 나누면 나머지가 0이다.  두 수의 차를 m으로 나눌 수 있으면, 두 수를 m으로 나눈 나머지는 동일하다. Example: 175(mod 6) 6|(17–5), (17–5)%6 = 0

Spiral Visualization of mod The Integers and Division Example shown: modulo-5 arithmetic ≡ 0 (mod 5) 20 15 10 ≡ 1 (mod 5) 5 ≡ 4 (mod 5) 19 21 14 16 9 11 4 6 1 3 2 8 7 13 12 18 17 ≡ 2 (mod 5) ≡ 3 (mod 5) 22 5로 나누어 나머지가 3인 수

Useful Congruence Theorems The Integers and Division Let a,bZ, mZ+. Then: ab (mod m)  kZ a=b+km. Let a,b,c,dZ, mZ+. Then if ab (mod m) and cd (mod m), then: (a와 b가 m 모듈로 합동이고, c와 d가 m 모듈로 합동이면,) a+c  b+d (mod m), and ac  bd (mod m) 나머지 몫

Applications of Congruence (합동의 응용) The Integers and Division The mod operator is widely used in hash functions. h(key) = key mod m Linear congruential methods is used to generate pseudo random numbers. x[n+1] = (a·x[n] + c) mod m  (생략) Also, in cryptography, encryption, …