# Elementary Number Theory and Methods of Proof

**Proof and Counterexample**

• Discovery and proof

• Even and odd numbers

– number n from Z is called even if
∃k
∈ Z, n = 2k

– number n from Z is called odd if
∃k
∈ Z, n = 2k + 1

• Prime and composite numbers

– number n from Z is called prime if

∀r, s ∈ Z, n = r * s
→ r = 1 ν s = 1

– number n from Z is called composite if

∃ r, s ∈ Z, n = r * s
Λ r > 1 Λ s > 1

**Proving Statements**

• Constructive proofs for existential statements

• Example: Show that there is a prime number that

can be written as a sum of two perfect squares

• Universal statements: method of exhaustion and

generalized proof

• Direct Proof:

– Express the statement in the form:
∀x ∈ D, P(x)
→

Q(x)

– Take an arbitrary x from D so that P(x) is true

– Show that Q(x) is true based on previous axioms ,

theorems, P(x) and rules of valid reasoning

**Proof**

• Show that if the sum of any two integers is

even, then so is their difference

• Common mistakes in a proof

– Arguing from example

– Using the same symbol for different variables

– Jumping to a conclusion

– Begging the question

**Counterexample**

• To show that the statement in the form “∀X ∈ D,

P(x) → Q(x)” is not true one needs to show that

the negation, which has a form “∃X ∈ D, P(x)
Λ

~Q(x)” is true. x is called a counterexample.

• Famous conjectures:

– Fermat big theorem: there are no non- zero integers x, y,

z such that x^{n} + y^{n} = z^{n}, for n > 2

– Goldbach conjecture: any even integer can be

represented as a sum of two prime numbers

– Euler’s conjecture: no three perfect fourth powers add

up to another perfect fourth power

**Exercises**

• Any product of four consecutive integers is

one less than a perfect square

• To check that an integer is a prime it is

sufficient to check that n is not divisible by

any prime less than or equal to Ön

• If p is a prime, is 2^{p} – 1 a prime too?

• Does 15x^{3} + 7x^{2} – 8x – 27 have an integer

zero?

• Real number r is called rational if

∃p,q ∈ Z, r = p / q

• All real numbers which are not rational are

called irrational

• Is 0.121212… a rational number

• Every integer is a rational number

• Sum of any two rational numbers is a

rational number

**Divisibility**

• Integer n is a divisible by an integer d, when

∃k ∈ Z, n = d * k

• Notation: d | n

• Synonymous statements:

– n is a multiple of d

– d is a factor of n

– d is a divisor of n

– d divides n

• Divisibility is transitive: for all integers a, b, c, if a

divides b and b divides c, then a divides c

• Any integer greater than 1 is divisible by a prime

number

• If a | b and b | a, does it mean a = b?

• Any integer can be uniquely represented in the

standard factored form:

is a

prime number

**Exercises**

• Prove or provide counterexample:

– For integers a, b, c: (a | b) → (a | bc)

– For integers a, b, c: (a | (b + c)) → (a | b Λ a | c)

• If 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * m = 151 * 150 *

149 * 148 * 147 * 146 * 145 * 144 * 143, does

151 | m?

• Show that an integer is divisible by 9 iff the sum

of its digits is divisible by 9. Prove the same for

divisibility by 3.

• Show that an integer is divisible by 11 iff the

alternate sum of its digits is divisible by 11

**Quotient and Remainder**

• Given any integer n and positive integer d, there

exist unique integers q and r, such that n = d * q +

r and 0 ≤ r < d

• Operations: div – quotient, mod – remainder

• Parity of an integer refers to the property of an

integer to be even or odd

• Any two consecutive integers have opposite parity

• The square of an odd integer has reminder 1 when

divided by 8 (read in book)

**Exercises**

• Show that a product of any four consecutive

integers is divisible by 8

• Show that the sum of any four consecutive

integers is never divisible by 4

• Show that any prime number greater than 3

has remainder 1 or 5 when divided by 6

Prev | Next |