Greek Number Theory

Greek Number Theory

 

1. Special numbers; square, triangular, prime, perfect

 (1) Square number

 

(2) Triangular number

 

(3) Prime number

The natural numbers with no divisors other than 1 and themselves

ex) 18=2*9=1*18 → not prime, has factors(1, 2, 9, 18, ect)

     19=1*19 → prime

Euclid say that...

Prime numbers are more than any assigned multitude of prime numbers.

(In modern them, the set of prime numbers is infinite.)

proof) Suppose there were only a finite number of primes,
Say p1, p2, …pn, for some n.(n is natural number.)
N=p1*p2*p3*…*p(n-1)*pn+1N is not divisible by any prime pi.
(i is the natural number which 1≤i≤n.)
ⅰ) N is prime: impossible since it is not in the list of prime(p1~pn).
ⅱ) N is composite: but any prime factor is a new prime not on list.
∴ The set of prime numbers is infinite.

Fundamental theorem of arithmetic

Every natural number can be written as a product of primes, in essentially one way(up to re-arrangement).

ex) 612=2*306=2*2*153=…=2*2*3*3*17

 

(4) Perfect number

A number is perfect means that the sum of all its divisors less than itself is the number.

ex) 12: 1+2+3+4+6≠12
      7: 1≠7
      6: 1+2+3=6
      28: 1+2+4+7+14=28

If 1+2+4+8+…+2n-1 is prime, than (1+2+4+8+…+2n-1)*2n-1 is perfect.

(Restatement → 2n–1 is prime, than (2n–1)*2n-1 is perfect.)

ex) 1+2 is prime ⇒ (1+2)*2=6 is perfect 1+2+4 is prime ⇒ (1+2+4)*4 is perfect

      1+2+4+8+16 is prime ⇒ (1+2+4+8+16)*16=496 is perfect

      1+2+4+8+…+2n-1=2n-1: Mersenne primes(if it is prime)

Number theory, especially prime numbers are very important in security field.

ex) nextprime(6191817543)=? (Nobody else can know, except you.)

 

2. Euclidean algorithm for greatest common divisors and continued fractions

gcd(a, b): the largest common divisor

ex) 612=22*32*17, 93=3*31

gcd(612, 93)=3

Euclidean algorithm

612=6*93+54

93=1*54+39

54=1*39+15

39=2*15+9

15=1*9+6

9=1*6+3

6=2*3+0 ⇒ 3 is gcd of 612 and 93

Continued fractions  

   → continued fraction

 

3. Pell’s equation and Cattle problem for Archimedes

There are infinite number of pairs of x and y which meet x2-Ny2=1 when N is fixed non-square natural number.Using this equation, we can find rational number x/y close to (N)1/2.

(1, 0) is the solution of all the Pell’s equations.

  Cattle problem

Compute, O friend, the number of the cattle of the sun which once grazed upon the plains of Sicily, divided according to color into four herds, one milk-white, one black, one dappled and one yellow. The number of bulls is greater than the number of cows, and the relations between them are as follows: If thou canst give, O friend, the number of each kind of bulls and cows, thou art no novice in numbers, yet can not be regarded as of high skill. Consider, however, the following additional relations between the bulls of the sun: White bulls + black bulls = a square number, Dappled bulls + yellow bulls = a triangular number. If thou hast computed these also, O friend, and found the total number of cattle, then exult as a conqueror, for thou hast proved thyself most skilled in numbers.

  

  Get Pell’s equation...  

   

 

References

http://www.youtube.com/watch?v=cUpSY0KlsA0

http://www.youtube.com/watch?v=VTU2imnzgwQ

http://en.wikipedia.org/wiki/Archimedes'_cattle_problem

참고하실 경우에 반드시 이 글 주소를 출처로 남겨주세요.