Page 95 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

The next proposition is short and sweet.

Proposition 5.1.2 (Shortbread Proposition (SP)). Let a ∈ Z , a =0. Then for any prime number p ,
either (a, p)= 1 or (a, p)= p , and p|a .

Proof: By definition, (a, p) is the largest integer which divides both a and p . The definition of prime
means that the only positive integers which divide p are 1 and p . Since (a, p) must divide p, this
means that either (a, p)= 1 or (a, p)= p . If (a, p)= p , by definition of (a, p), p|a .

♥

To understand the FTA, we need to define a finite sequence.

Definition 5.1.3 A finite sequence is a list of n elements with a specific order, where n ∈ N .

A finite sequence is similar to an indexed finite set with one key difference:

a finite sequence may contain the same element repeated multiple times.

The set

{3}

is the same as the set {3, 3} . But, the finite sequence

{3}

is not the same as the finite sequence

{3, 3}.

In the definition of finite sequence, the finite sequence {3} is the list which contains one element, the
number 3. So, the role of n in the definition of finite sequence is played by 1. On the other hand, the
finite sequence {3, 3} is the element 3 listed twice, so the role of n is played by 2. So, these are different
finite sequences. Since the same notation {} is used for both sets and finite sequences, we must always
state whether we are using the notation to indicate a set or a finite sequence.

Exercise: For the finite sequence {1, 4, 4, 5} , which natural number plays the role of n in the definition
of finite sequence?

95