이산수학(Discrete Mathematics)  정수와 나눗셈 (The Integers and Division)

Slides:



Advertisements
Similar presentations
10-7 부동소수점 (Floating-Point) 계산  컴퓨터에서 숫자를 표기하는 방법  가수 (Fraction) : 부호화된 고정소수점 숫자 지수 (Exponent) : 소수점의 위치를 표시 ( 예 )10 진수 를 표기하면 Fraction Exponent.
Advertisements

명륜종합사회복 지관. * 강사 : 소 찾는 아이 작가 이상희, 김매화 팀장 외 * 북아트란 : 논술교육의 중요성, 자유로운 사고, 창 의력, 논리력 * 준비물 : 색연필, 사인펜, 연필, 지우개, 딱풀, 가위.
1.다음 동물들을 조류와 포유류로 분류하여 빈 곳에 써 넣어라.
ALL IN ONE WORKING HOLIDAY!
Chapter 9 암호 수학 III 소수와 연관된 합동방정식
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
이산수학(Discrete Mathematics)
(Mathematical Induction)
C++ Tutorial 1 서강대학교 데이터베이스 연구실.
Compiler Lecture Note, Inroduction to FL theory
Nested Queries CSED421: Database Systems Labs.
이산수학(Discrete Mathematics)  정수와 나눗셈 (The Integers and Division)
6.9 Redundant Structures and the Unit Load Method
기본 컴퓨터 프로그래밍 Lecture #6.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
제 5 장 암호학의 수학기초 Network Security Lab Mun Hyung Jin.
이산수학(Discrete Mathematics)
Discrete Math II Howon Kim
부울대수(Boolean Algebra)
DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003.
이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
2주차 – 수학적 배경 주교재 2장.
Chapter 7. PUSHDOWN AUTOMATA Exercises
고대수학 1. 바빌로니아 이집트 그리스 인도 아랍 중국 미대륙.
제 14 장 거시경제학의 개관 PowerPoint® Slides by Can Erbil
Chapter 2. Finite Automata Exercises
Discrete Math II Howon Kim
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
Modulo 연산.
전자상거래 보안 (암호학과 네트워크보안) Chul Ho Rhee
계수와 응용 (Counting and Its Applications)
이산수학(Discrete Mathematics)
PCA Lecture 9 주성분 분석 (PCA)
우리생활속의 확률 이용사례탐구 한림초등학교영재학급 6학년 김수민.
1.4 중첩된 한정기호 (Nested Quantifiers) 이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
(Relations and Its Properties)
제 4 장. Regular Language의 특성
Mathematical Description of Continuous-Time Signals
Linux/UNIX Programming
오늘의 주제 : 수학과 문명의 발달.
Linux/UNIX Programming
Introduction to Programming Language
Discrete Math II Howon Kim
이산수학(Discrete Mathematics)
연구실 소개 서울대학교 수리과학부 교수 천정희.
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics)  명제의 동치 (Propositional Equivalence)
Discrete Math II Howon Kim
제 5장 공개키 암호.
Linux/UNIX Programming
Linux/UNIX Programming
이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics) 비둘기 집 원리 (The Pigeonhole Principle)
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  집합 연산 (Set Operations)
점화와 응용 (Recurrence and Its Applications)
The World of English by George E.K. Whitehead.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
2.7 행렬 (Matrices] 이산수학 (Discrete Mathematics) Matrix Reloaded
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
문장제 쉽게 풀기 -최소공배수 응용 문제.
(Predicates and Quantifiers)
이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers)
[CPA340] Algorithms and Practice Youn-Hee Han
(Permutations and Combinations)
Linux/UNIX Programming
Presentation transcript:

이산수학(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, …