This seminar by pyninja took place on 17 August 2008 16:00 UTC, in #mathematics channel of

The timestamps displayed in the IRC text are UTC+1.
Any explanation or errors regarding this seminar should be recorded in the discussion page.

Topic Edit

Introduction to Number Theory. Modular arithmatic, properties of prime numbers.

Seminar Edit

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
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
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
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
         Other seminars (past and future):
         You probably want to join #math until the seminar starts