Chp1. 소인수분해

본론
1-1 소수와 합성수
01.소수
1보다 큰 자연수에서 1과 자기 자신만을 약수로 가지는 수-약수가 2개뿐인 수-
소수중 짝수는 2뿐이고 나머지는 모두 소수이다
02.합성수
1보다큰 자연수에서 소수가 아닌수
약수가 3개 이상인 자연수
***1은 소수도 아니고 합성수도 아니다***
03.자연수의 구성
1,소수,합성수

1-2 소인수분해-1
01.거듭제곱
같은수나 문자를 반복해서 곱한것
2*2 = 2^2 - 2의 제곱
2*2*2 = 2^3 - 2의 3제곱,이때 2는 밑 3은 지수라 한다
02.소인수분해
자연수를 소인수들만의 곱으로 나타낸것
=인수a가 자연수 b와 c의 곱으로 표현하는것
=즉 a=b*c일때 b,c를 a의 인수라 하고 b,c가 소수로 표현하는것,
(소인수=이런 인수들중 소수인것)
03.소인수분해 방법
수a를 나누어 떨어지게 하는 소수중 작은수로부터 나누는것

1-3 소인수분해-2
01.소인수분해를 이용한 약수 구하기
자연수의 약수를 모두 구할때 소인수 분해를 이용해 할수 있다.
-거듭제곱의 형태(x=a^n)
약수의 개수=n+1개
-다수의 분해 형태 (x=a^n * b^m)
약수의 개수 = (m+1) *(n+1) 개

1-4 공약수와 최대공약수
01.공약수와 최대공약수란?
공약수=두개이상의 자연수의 공통인 약수
ex)8의 약수=1,2,4,8 12의 약수=1,2,3,4,6,12   공약수=1,2,4
최대공약수=공약수 중에서 가장 큰수
최대공약수의 성질=두개 이상의 자연수의 공약수는 최대공약수의 약수이다
ex)8과 12의 공약수인 1,2,4는 8과 12의 최대공약수인 4의 약수
서로소:최대공약수가 1인 두개의 자연수
**최대공약수를 GCD(Greatest common Divisor) 로 표기한다
**공약수중 가장 작은수는 항상 1이라 "최소공약수"는 언제나 1이라 생각하지 않는다
02.최대공약수 구하는 방법
1.소인수분해법
각각의 수를 인수분해한다
공통인 소인수의 거듭제곱에서 지수가 "작거나 같은것"을 곱한다
ex)54=2*3^3 , 90=2*3^2*5, 2*3^2=18
2.공약수로 나누어 구하는 방법
1이외의 공약수로 각수를 나눈다
몫에 1이외의 공약수가 없을때(서로소)까지 공약수로 계속 나눈다
나눈 공약수를 모두 곱한다
ex) 2|12 36 42
3|6  18 21
  ---------
  2  6   7
  최대공약수=2*3

1-5 공배수와 최소공배수

01.공배수와 최소공배수란?
공배수=두개 이상의 자연수의 공통인 배수
ex) 3의배수 3,6,9,12,15,18
4의배수 4,8,12,16,20
공배수=12,24
최소공배수=공배수중 가장 작은수
ex)3,4의 공배수는 12,24,...에서 최소공배수는 12이다
최소공배수의 성질=두개 이상의 자연수의 공배수는 최소공배수의 배수이다
ex)3과 4의 공배수인 12,24는 3과 4의 최소 공배수인 12의 배수이다
서로소인 두 자연수의 최소공배수는 두 자연수를 곱한수이다
**최소공배수는 LCM(Least Common Multiple) 로 나타낸다
**배수는 무한히 커지기 때문에 "최대공배수"는 존재하지 않는다**

02.최소공배수 구하기
1.소인수분해를 이용하는 방법
각수를 소인수분해한다
공통인 소인수와 공통이 "아닌" 소인수를 모두 곱한다, 이때 "지수가 크거나 같은것"을 택한다
ex) 108=2^2*3^3  270=2*3^3*5
최소공배수=2^2 * 3^3 * 5=540
2.공약수로 나누어서 구하기
1이외의 공약수로 나눈다
3개의 수의 공약수가 없으면 2수의 공약수로 나누고 나머지를 내린다
모든수가 서로소가 될때까지 반복한다
나눈수와 마지막 몫 을 모두 곱한다
ex) 2| 18 28 42
3| 9  14 21
  ---------
  3    2  1
  =2*3*7*3*2*1=251

03.최대공약수와 최소공배수의 관계
두 자연수 A,B의 최대 공약수가 G이고 최소공배수가 L일때 A,B를 G로 나눈 몫을 각각 a,b(a,b는 서로소)에서 다음이 성립한다
L=g*a*b
A=G*a,B=G*b==>A*B=G*L

1-6 최대공약수와 최소공배수의 활용
01.최대공약수의 활용
"가능한 많은 최대값", "가능한 큰" 의 말이 나올때 최대공약수로 해결
02.최소공배수의 활용
"가능한 적은","최소의","가능한 작은"의 말이 나올때 최소공배수로 해결