Combinatorial probability

Let us repeat our experiment n times. A possible outcome of this repeated experiment is a sequence of length n, consisting of elements of S. Thus the sample space corresponding to this repeated experiment is the set Sn of such sequences. Thus the number of outcomes of this “big” experiment is kn. We consider every sequence equally likely, which means that we consider it a uniform probability space. Thus if (a1,a2,...,an) is an outcome of the “big” experiment, then we have

P(a1,a2,...,an) = ^1/_k^n

As an example, consider the experiment of tossing a coin twice. Then S = {H,T} (head,tail) for a single coin toss, and so the sample space for the two coin tosses is {HH,HT,TH,TT}. The probability of each of these outcomes is 1/4.

7.1 What event does the union of two subsets corresponds to?

The union of two events A and B corresponds to “A or B”.

7.2 Prove that the probability of any event is at most 1.

It is the sum of some of the probabilities of outcomes, and even if add all we get just 1.

7.3 What is the probability of the event E that we throw an even number with the dice? What is the probability of the event T = {3,6} that we toss a number that is divisible by 3?

P(E)=1/2, p(T)=1/3

7.4 Prove that if A and B are exclusive, then P(A) + P(B) = P(A ∩ B).

The same probabilities P(s) are added up on both sides.

7.5 Prove that for any two events A and B,

P(A∩B)+P(A∪B) = P(A)+P(B).

Every probability P(s) with s ∈ A ∩ B is added twice to sides; every probability P(s) with s ∈ A∪B but s ∈/ A∩B is added once to both sides.

7.6 Which pairs of the events E,O,T,L are independent? Which pairs are exclusive?

The pairs (E,T),(O,T),(L,T) are independent. The pair (E,O) is exclusive.

Integers, divisors, and primes

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103

“Fundamental Theorem of Number Theory”: Every positive integer can be written as the product of primes, and this factorization is unique up to the order of the prime factors.

Euclid: Theorem 8.3 There are infinitely many primes.

What we need to do is to show that for every positive integer n, there is a prime number larger than n. To this end, consider the number n! + 1, and any prime divisor p of it. We show that p > n. Again, we use an indirect proof, supposing that p ≤ n and deriving a contradiction. If p ≤ n then p|n!, since it is one of the integers whose product is n!. We also know that p|n!+1, and so p is a divisor of the difference (n!+1)−n! = 1. But this is impossible, and thus p must be larger than n.

Theorem 8.5 (The Prime Number Theorem) Let π(n) denote the number of primes among 1,2,...,n. Then pi(n)~n/ln n

the “Little” Theorem of Fermat: If p is a prime and a is an integer, then p|a^p − a.

Last Fermat theorem: If n > 2, then the sum of the n-th powers of two positive integers is never the n-th power of a positive integer. (The assumption that n > 2 is essential: there are many exam- ples of two squares whose sum is a third square: for example, 32+42 =52,or52+122 =132)

Theorem 8.2 The number ^√2 is irrational.

We give an indirect proof again: we suppose that ^√2 is rational, and derive a contradiction. What the indirect assumption means is that ^√2 can be written as the quotient of two positive integers: ^√2 = ^a. Squaring both sides and rearranging, we get 2b^2 = a^2. Now consider the prime factorization of both sides, and in particular, the prime number 2 on both sides. Suppose that 2 occurs m times in the prime factorization of a and n times in the prime factorization of b. Then it occurs 2m times in the prime factorization of a2 and thus it occurs 2m + 1 times in the prime factorization of 2a2. On the other hand, it occurs 2n times in the prime factorization of b2. Since 2a2 = b2 and the prime factorization is unique, we must have 2m+1 = 2n. But this is impossible since 2m+1 is odd but 2n is even. This contradiction proves that ^√2 must be irrational.

Another famous unsolved problem is Goldbach’s conjecture. This states that every even integer larger than 2 can be written as the sum of two primes. Goldbach also formulated a conjecture about odd numbers: every odd integer larger than 5 can be written as the sum of three primes.

The greatest common divisor of two positive integers a and b. This is defined as the largest positive integer that is a divisor of both of them. A somewhat similar notion is the least common multiple of two integers, which is the least positive integer that is a multiple of both integers, and denote by lcm(a,b). The greatest common divisor of two positive integers can be found quite simply by using their prime factorizations: look at the common prime factors, raise them to the smaller of the two exponents, and take the product of these prime powers.

Now we turn to Euclid’s Algorithm. Let a and b be two positive integers, and suppose that a < b. The algorithm is based on two simple facts.

Suppose that we are given two positive integers a and b, and we want to find their g.c.d. Here is what we do:

1. If a > b then we interchange a and b.


2. Ifa>0,divide b by a, to get a remainder r. Replace b by r and return to 1.

3. Else (if a = 0), return b as the g.c.d. and halt.

8.3 Prove that

(a) if a|b and b|c then a|c;

(b) if a|b and a|c then a|b+c and a|b−c;

(a)Ifb=am andc=bn thenc=amn. (b)Ifb=am andc=an thenb+c=a(m+n) and b−c=a(m−n). (c)Ifb=am anda,b>0 thenm>0,hencem≥1 andsob≥a. (d)Trivialif a = 0. Assume a ̸= 0. If b = am and a = bn then a = amn, so mn = 1. Hence either m = n = 1 or m = n = −1.

8.7 Are there any even primes? How many?

The number 2