English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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 xn + yn = zn, 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 2p – 1 a prime too?

• Does 15x3 + 7x2 – 8x – 27 have an integer
zero?

Rational Numbers

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