Week 9 - Number Theory

1. History of Mathematics

• Mathematics has evolved over thousands of years.
• Some important mathematicians

Euclid:

• Famous for work on geometry.
• Known for “Pythagorean theorem”

Fermat:

• Worked in number theory.
• Known for “Last Theorem”.

Euler:

• Worked on calculus, number theory, and graph theory. Example: Euler’s identity: e^(iπ) + 1 = 0.

Gauss:

• Known as the “Prince of Mathematicians.”
• Made contributions to number theory and algebra.
• Known for Gaussian integers

Archimedes:

• Worked on geometry and developed the concept of pi.

Indian Mathematician: Srinivasa Ramanujan

• Self-taught mathematician who contributed to number theory.
• Worked with G.H. Hardy on partitions and mock theta functions.

2. Number Theory

• Deals with properties and relationships of numbers, particularly integers.
• Includes concepts such as divisibility, prime numbers, and greatest common divisor.

Example: 13 is a prime number, but 15 is not because it is divisible by multiple numbers.

3. Magic Square

• A square grid of numbers where each row, column, and diagonal has the same sum.
• Used in recreational mathematics.

Example: 3x3 magic square:

4 9 2
3 5 7
8 1 6

4. Theory of Partitions

• Deals with ways a number can be expressed as a sum of other numbers.
• Uses the partition function to count the number of ways.

Example: The partition function of 4 is 5:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

5. Division Algorithm

• Any two positive integers can be written uniquely as a quotient and a remainder.
• Uses the mod function. a = qb + r where a & b are integers and q & r are quotient and remainder respectively.

Example: 17 divided by 5 is 3 with a remainder of 2, written as 17 = 3(5) + 2.

6. GCD

• Greatest common divisor is the largest positive integer that divides two integers.
• Can be found using the Euclidean algorithm.

7. Euclidean Algorithm

• Uses division algorithm to find the GCD of two integers.
• Repeatedly divides the larger number by the smaller number and replaces the larger number with the remainder until the remainder is 0.

To find the GCD of 48 and 60 using the Euclidean algorithm:

1. Divide 60 by 48 to get 1 remainder 12.
2. Divide 48 by 12 to get 4 remainder 0.
3. The last nonzero remainder is 12, so that is the GCD. Therefore, the GCD of 48 and 60 is 12.

Example 2: GCD of 18 and 24: 24 = 1(18) + 6 18 = 3(6) + 0 GCD is 6.

8. Prime Numbers

• A prime number is only divisible by 1 and itself.
• Important in number theory and cryptography.

Example: 2, 3, 5, and 7 are prime numbers.

9. Fundamental Theorem of Arithmetic

• Every positive integer can be expressed uniquely as a product of prime numbers.

Example: 24 can be expressed as 2 * 2 * 2 * 3.

10. Prime Factor Test

• Determines whether a composite integer has prime factors.
• Composite number - that is not a prime number and can be divided by numbers other than 1 and itself.

Example:

1. The square root of 27 is approximately 5.196.
2. We only have to check the test till 5.
3. 27 is not divisible by 2 but divisible by 3.
4. Since 27 is divisible by a number(3) other than 1 and itself,
   therefore 27 is not a prime number.

11. Divisibility

• One integer divides another if it is a factor of that integer.
• Useful in number theory and algebra.

Example: 6 is divisible by 3 because 6 divided by 3 equals 2 with no remainder.