Introduction to Number Theory. Modular arithmatic, properties of prime numbers.
17:00:00 ChanServ changed the topic of #mathematics to: SEMINAR IN PROGRESS. If you want to speak, say ! and wait to be called 17:00:25 pyninja: alright 17:00:39 pyninja: I'm going to start with the Fundamental Theorem of Arithmetic. 17:01:21 pyninja: The FTA states that all positive integers greater than 1 have a unique prime factorization. 17:03:53 pyninja: All positive integers n>1 can be uniquely represented in the form p_1^(e_1) * p_2^(e_2) * ... * p_k^(e_k), where p_i are distinct primes in increasing order and e_i are positive integers. 17:04:50 pyninja: The proof of this relies on Bezout's lemma, which is: 17:05:40 pyninja: For positive integers m,n, with d=gcd(m,n), there exist coefficients x,y such that x*m + y*n = d. 17:06:46 pyninja: Furthermore, x*m + y*n = k has integer solutions if and only if d|k. 17:07:36 pyninja: To prove this, we can let S be the set of all positive integers in the form x*m + y*n with smallest element c = a*m + b*n. 17:08:16 pyninja: Since m is in S, c <= m, so by the division algorithm, we can write m = q*c + r 17:08:31 pyninja: where q, r are integers with 0 <= r < c. 17:08:56 pyninja: We can rearrange to get r = m - q*c = m - q*(am+bn) 17:09:10 pyninja: so r = (1-qa)*m + (-b)*n. 17:09:29 pyninja: Therefore, r is either an element of S, or is 0. 17:09:46 pyninja: But since r<c, and c is the smallest element of S, r must be 0. 17:10:02 pyninja: So m=qc and c|m. 17:10:17 pyninja: We can show c|n in the same way. 17:11:07 pyninja: Note that gcd(m,n) divides all elements of S, so gcd(m,n)|c. 17:11:34 pyninja: But c is a common factor of m,n so c|gcd(m,n). 17:11:49 pyninja: Therefore, c=gcd(m,n) as claimed. 17:12:34 pyninja: So that's the proof of Bezout's lemma. 17:12:51 pyninja: We're going to use this to show that if p is prime and p|ab, then either p|a or p|b. 17:13:09 pyninja: If p|a then we're done. 17:14:09 pyninja: Otherwise, gcd(p,a)=1 so there exist x,y such that x*p + y*a = 1. 17:14:45 pyninja: Multiplying by b, this becomes xpb + yab = b. 17:15:06 pyninja: Note that p|p, so p|xbp, and p|ab, so p|yab. 17:15:36 pyninja: Therefore, the LHS is divisible by p, so the RHS must also be divisible by p. 17:15:48 pyninja: i.e., p|b and we're done. 17:16:19 pyninja: We use the argument in reverse to show that if p doesn't divide b then it must divide a. 17:17:01 pyninja: So from this it follows that p|a*b*...*k implies p|a or p|b or ... p|k. 17:17:32 pyninja: Now we can prove the Fundamental Theorem of Arithmetic: 17:18:37 pyninja: Suppose n has two different prime factorizations, that is, n = p_1^(a_1) * ... * p_s^(a_s) = q_1^(b_1) * ... * q_t^(b_t). 17:19:44 pyninja: Then by what just proved, we must have p_i|q_1^(b_1)*...*q_t^(b_t) for every i. 17:19:57 pyninja: So for every i there is a j such that p_i = q-J. 17:20:03 pyninja: p_i = q_j. 17:20:20 pyninja: Similarly, for every i there is a j such that q_i = p_j. 17:20:54 pyninja: Therefore, s=t (both representations have the same number of primes), and p_i = q_i for all i. 17:21:03 pyninja: (since both sets are arranged in increasing order) 17:21:18 pyninja: Now suppose we have a_i > b_i for some i. 17:22:31 pyninja: Then we can divide both sides by p_i^(b_i) to get p_1^(a_1) * ... * p_i^(a_i - b_i) * ... * p_s^(a_s) = p_1^(b_1) * ... * p_(i-1)^(b_i-1) * p_(i+1)^(b_i+1) * ... * p_t^(b_t). 17:24:02 pyninja: But now the LHS is divisible by p_i, while the RHS is not. 17:24:21 pyninja: We get the same contradiction if b_i > a_i for some i. 17:24:31 pyninja: So, a_i = b_i for all i. 17:24:57 pyninja: And we're done: all positive integers greater than 1 have a unique prime factorization. 17:25:24 pyninja: A famous consequence of this is that there are infinitely many primes. 17:26:27 pyninja: This follows when you assume the contrary and look at the number that is the product of all the primes, plus 1. 17:27:09 pyninja: There are some other proofs too, but I feel like moving to congruences now. 17:27:55 pyninja: If m|x-y, we write x=y (mod m). 17:28:11 ~astrophil: ! 17:28:17 pyninja: yes? 17:28:38 ~astrophil: Can you briefly define 'infinitely many primes'? 17:29:01 pyninja: The set of primes is infinite. 17:29:13 pyninja: There is no largest prime. 17:29:28 ~astrophil: Can we say there are 'infinite primes'? 17:30:00 _llll_: no 17:30:23 ~astrophil: Ok. 17:30:36 pyninja: :) 17:30:36 _llll_: every prime is finite. there are infinitely many of them. just like every number is finite but there are infinitely mnay of them 17:30:48 pyninja: right 17:31:18 ~astrophil: Ok, got it. 17:31:17 pyninja: Okay, so m|x-y is equivalent to x=y (mod m). 17:31:38 pyninja: This notation has some advantages in some contexts. 17:32:00 pyninja: Here, y is called a residue of x (mod m). 17:32:29 pyninja: A class of residues (mod m) consists of all numbers congruent to a given residue (mod m). 17:32:51 pyninja: For example, 2008 = 8 = -2 (mod 10). 17:33:23 pyninja: By the way, I forgot to mention that the equality sign used for congruencies has 3 bars. 17:33:45 pyninja: I'm just using = for convenience. 17:34:08 pyninja: There are 10 residue classes (mod 10), represented by 0, 1, 2, ..., 9. 17:34:28 pyninja: Some properties of congruences: 17:34:51 pyninja: Addition: a+b (mod m) = a (mod m) + b (mod m). 17:35:09 pyninja: Multiplication: ab (mod m) = (a (mod m))(b (mod m)). 17:35:39 pyninja: Division: ka = kb (mod m) <=> a=b (mod m) if, and ONLY if, gcd(k,m) = 1. 17:36:14 pyninja: Exponentiation: a^k (mod m) = (a (mod m))^k. 17:37:13 pyninja: So for example, 123456789^2 (mod 10) = 9^2 (mod 10) = (-1)^2 (mod 10). 17:37:32 pyninja: Also note that x (mod 10) is just he last digit of x. 17:37:45 pyninja: the last digit* 17:39:14 pyninja: This notation is useful for solving linear equations, for example. 17:40:00 pyninja: Consider the equation 5x + 7y = 2008. 17:40:07 pyninja: where x,y are integers. 17:40:27 pyninja: If we look at this equation (mod 5), we get: 17:40:34 pyninja: 2y = 3 (mod 5). 17:40:57 pyninja: which is equivalent to 2y = 8 (mod 5). 17:41:28 pyninja: since 2,5 are relatively prime, this means y = 4 (mod 5). 17:42:19 pyninja: That gives us an initial solution from which we can easily get the general solution. 17:43:07 pyninja: Next let's look at the totient function. 17:44:30 pyninja: The totient function is called phi(n) and is equal to the number of positive integers k <= n with gcd(k,n) = 1. 17:44:47 pyninja: (if gcd(a,b) = 1, a and b are relatively prime or coprime) 17:45:55 pyninja: So for example, phi(9) = 6 because 1, 2, 4, 5, 7 are relatively prime to 9. 17:46:03 pyninja: and also 8. 17:46:52 pyninja: It's not hard to find phi(n) once we have the prime factorization of n. 17:47:45 pyninja: In fact, phi(p_1^(e_1)*p_2^(e_2)*...*p_k^(e_k)) = n * (1-1/p1))*(1-1/p_2)*...(1-1/p_k). 17:48:20 pyninja: This function turns out to be very useful. 17:48:46 pyninja: Euler's totient theorem states that a^(phi(n)) = 1 (mod n), for all relatively prime a,n. 17:49:36 pyninja: So for example, if you wanted to find the last 2 digits of 2^2008, you need to find 2^2008 (mod 100) 17:49:59 pyninja: actually, that wouldn't work so great because 2 and 100 are not relatively prime 17:50:21 pyninja: But you can find 3^2008 (mod 100): 17:50:36 pyninja: Since phi(100) = 40, 3^40 = 1 (mod 100). 17:50:49 pyninja: So we just need to find 3^8 (mod 100). 17:51:17 pyninja: Because 3^2008 = (3^40)^50 * 3^8. 17:51:57 pyninja: It also has many other more useful / interesting applications. 17:52:53 pyninja: Let's look at some diophantine equation.s 17:53:12 pyninja: (Diophantine equations are equations in integers.) 17:55:23 pyninja: Okay, a Pythagorean triple (a,b,c) is a set of integers that satisfies the Pythagorean thoerem, a^2 + b^2 = c^2. 17:56:13 pyninja: a triple is called primitive if all three numbers are relatively prime. 17:57:17 pyninja: all primitive triples are in the from (m^2 - n^2, 2mn, m^2 + n^2). 17:57:31 pyninja: (or (2mn, m^2-n^2, m^2+n^2)) 17:58:17 pyninja: I don't think I have time to go through the whole solution, but basically you look at parity (mod 2) and (mod 4). 17:58:55 pyninja: (first of all, both a,b can't be odd) 17:59:09 pyninja: but I think I should just stop here. 17:59:36 pyninja: You can ask questions if you have any. 17:59:48 pyninja: I probably bored most people... 18:00:00 ~Bassoon: Hardly. 18:00:22 pyninja: That's good :) 18:00:49 ~Copycat: i didnt understand that phi(p_1^(e_1)*p_2^(e_2)*...*p_k^(e_k)) = n * (1-1/p1))*(1-1/p_2)*...(1-1/p_k). 18:02:46 pyninja: Well, for example, let's look at phi(10). 18:03:25 pyninja: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 18:03:50 pyninja: We have to take out the multiples of 2 and the multiples of 5. 18:04:10 ~Copycat: its 1,3,7,9 18:04:21 pyninja: Right, so phi(10) = 4. 18:04:26 ~Copycat: phi(10)=4 18:04:43 ~Copycat: and the formula? 18:04:48 pyninja: phi(2*5) = 10*(1-1/2)*(1-1/5) = 4. 18:05:16 ~Copycat: interesting but how do i proove the formula? 18:06:09 _llll_: maybe helpful to start with phi(ab)=phi(a)*phi(b) if gcd(a,b)=1 18:06:14 kommodore: Copycat: inclusion-exclusion 18:06:15 pyninja: To prove it you use the fact that phi is multiplicative 18:06:19 pyninja: yes 18:06:57 pyninja: To prove that you have to look at the residue classes. 18:09:35 ~Copycat: thanks for the seminar 18:09:45 _llll_: is there more to come next week? 18:11:04 pyninja: Sure, I'll do it if people want me to. 18:15:03 ~Bassoon: I'd be back. 18:17:39 pyninja: how about Euler's Theorem and Diophantine Equations? 18:18:38 ChanServ changed the topic of #mathematics to: NEXT SEMINAR: Euler's Theorem and Diophantine Equations by pyninja on Sunday 24 August 16:00UTC | Transcript of last seminar http://www.freenode-math.com/index.php/Introduction_to_Number_Theory | Other seminars (past and future): http://www.freenode-math.com/index.php/Seminars | You probably want to join #math until the seminar starts