Chp04. 정수

04-1 정수의 분류



01.정수의 나눗셈
정수 a를 양의 정수 b로나눈 몫을 q 나머지를 r이라 했을 때 a=bq+r 이다



02.정수의 분류
정수를 어떻게 해야 나눌수 있을까?
짝수 , 홀수 로 나눌수 있다
==짝수는 2의 배수 또는 2로 나누어 떨어지는수 , 2n
==홀수는 2로 나누어서 나머지가 1인수 2n+1
로 구분이 가능하다


모든 양의 정수 k로 나눈 나머지에 의해 kn , kn+1 , kn+(k-1) *n은정수*



Ex)3으로 나누어 떨어지고 4로 나누면 나머지가 1인 정수를 정수 n을 사용해 가장 간단한 형태로 나타내기
==3으로 나누어 떨어지는수 = 3n
여기서 n을 4로 나눈수의 나머지는 0,1,2,3이므로 4n , 4n+1 , 4n+2 , 4n+3 이다


N=4n - 3(4n)=12n=4(3n)
N=4n+1 - 3(4n+1)=12n+3 = 4(3n)+3
N=4n+2 – 3(4n+2)12n+6 = 4(3n+1)+2
N=4n+3 – 3(4n+3) = 12n+9 = 4(3n+2)+3 

나머지가 1인 것 = 12n+9



04-02 정수의 약수와 배수 

01.약수와 배수의 정의
약수,배수 = 정수 a,b,q 사이에 a=bq 관계가 성립할 때
==A=b의 배수
==B=a의 약수
관계로 정의한다



02.배수에 관한 법칙
3자리 정수가 있을 때 100,10,1자리수를 각각 x,y,z로 하면 N은 100x + 10y + z 이다
--(99+1)x + (9+1)y + z =99x + 9y + x+y+z = 9(11x+y)+(x+y+z) 가 된다
이때 x+y+z가 3의 배수이므로 N도 3의배수 x+y+z가 9의 배수이면 n도 9의 배수이다



03.소수와 소인수 분해

소수
=2,3,5,7 과 같이 1보다 큰 자연수 중에서 약수를 1과 자기 자신 이외의 양의 약수를 가지지 않은 수



합성수
=1보다 큰수에서 소수가 아닌수 , 1은 소수도,합성수도 아니다



소인수 분해
=합성수는 항상 소수인 인수의 곱으로 나타낼수 있다, 이것을 소인수 분해라 한다
Ex)90을 소인수 분해시
2 | 90
5 | 45
3 | 9
-----
3
이다



Ex)360을 소인수 분해 하면?
2 | 360
2 | 180
3 | 90
3 | 30
2 | 10
-----
5
===2^3 * 3^2 * 5^1 =360 이다
이때 약수의 개수 = (지수 + 1) 의 곱이며 이때는 (3+1) * (2+1) * (1+1) = 24개임



**비둘기집 원리**
n개의 비둘기집에 n+1마리의 비둘기가 있을 때 적어도 1집에는 두마리 이상의 비둘기가 살고 있다,
ex)a 한변의 길이가 2인 정사각형의 내부에 점 5개를 찍으면 두점사이의 거리가 (근호)2보다 작은 두점이 존재함을 증명하라

각변의 중점을 이어서 4개로 나누면 어떻게 해도 5번째는 √2보다 가까워진다

04-3 최대공약수와 최소 공배수


01.정수의 최대 공약수와 최소 공배수
최대 공약수
=두개 이상의 정수의 공통약수를 공약수라 하고 공약수중 가장 큰 수를 최대 공약수라 한다
=GCD – Greatest Common Divison



서로소
=최대공약수가 1인 것



최소공배수
=두개 이상의 정수에서 공통인 배수들중 가장 작은수
=LCM – leatest Common Multiple



Ex)180과 72의 GCD와 LCM 을 구하라
180 = 2^2 * 3^2 * 5
72 = 2^3 * 3^2
GCD = 공통된 밑수에서 작은수의 곱 = 2^2 * 3^2
LCM = 공통된 밑수에서 큰것과 나머지 모든 것의 곱 = 2^3 * 3^2 * 5





02.최대 공약수와 최소 공배수의 관계
A , B에서 최대공약수를 G , 최소공배수를 L이라 할 때
A=Ga , B=Gb
L=Gab
Lg=ab 가 성립한다


Ex)곱이 360이고 최소공배수가 120인 두 자연수를 구하면?
A=Ga , B=Gb , AB=LG
==360=L*G – 360=120*3
최대공약수 G=3
L=Gab = 120=3*ab ab=40
Ab가 서로소 a>b일 때 [40,1] [8,5]
A=G*a 3*40 , 3*8
B=G*b 3*1 , 3*5
120 24
3 15



04-4 기수법

01 십진법 , p진법

십진법
==0~9까지 표기하고 각 자리수는 10의 거듭제곱 형태로 나타낸다


p진법


==p진법의 양의정수  

==p진법의 양의 소수

p진법을 r진법으로 바꾸기
p진법수 – 십진법수 - r진법수



ex)5진법 324 를 3진법으로 바꾸면?
3 * 5^2 * 2*5^1 + 4*5^0 = 89 십진법
3 | 89
3 | 29 ---2
3 | 9 ---2
3 | 3 ---0
----
1 ----0

10022 3진법이 완성됨