Proof By Exhaustion

Question 1

Suppose n is an integer between 24 and 28 inclusive.

Prove that n is not a prime number

Answer 1

• n = 24, 25, 26, 27 and 28
• ( You have to show that each of these are not prime numbers )
• ( You can do this by showing their factors )

Factors of 24:

1, 2, 3, 4, 6, 8, 12, 24, so 24 is not a prime number

Factors of 25:

• 1, 5, 25, so 25 is not a prime number

Factors of 26:

• 1, 2, 13, 26, so 26 is not a prime number

Factors of 27:

• 1, 3, 9, 27, so 27 is not a prime number

Factors of 28:

• 1, 2, 4, 7, 14, 28, so 28 is not a prime number
• If n is an integer between 24 and 28 inclusive, then n is not a prime number
• ( Always make conclusions from your results )

Question 2

Prove that all square numbers are either a multiple of 4 or 1 more than a multiple of 4

Answer 2

• ( Divide the statement into different cases )
• ( Square numbers can either be odd or even )
• Case 1, odd numbers
• Case 2, even numbers
• Odd numbers = 2n + 1
• ( 2n + 1 )^2 = 4n^2 + 4n + 1
• 4n ( n + 1 ) + 1
• 4n ( n + 1 ) is a multiple of four
• 4n ( n + 1 ) + 1 is 1 more than a multiple of 4
• Even number, 2n
• ( 2n )^2 = 4n^2
• 4n^2 is a multiple of 4
• So all square numbers are either a multiple of 4 or 1 more than a multiple of 4

Question 3

Prove that if n is an integer and 2 <= n <= 7, then A = n^2 + 2 is not divisible by 4. ( Numerically )

Answer 3

• ( We are looking at numbers 2, 3, 4, 5, 6 and 7 )
• ( 2 )^2 + 2 = 6, which is not divisible by 4
• ( 3 )^2 + 2 = 11, which is not divisible by 4
• ( 4 )^2 + 2 = 18, which is not divisible by 4
• ( 5 )^2 + 2 = 27, which is not divisible by 4
• ( 6 )^” + 2 = 38, which is not divisible by 4
• ( 7 )^2 + 2 = 51, which is not divisible by 4
• Hence if n is an integer and 2 <= n <= 7, then A = n^2 + 2 is not divisible by 4

Question 4

Prove that if n is an integer and 2 <= n <= 7, then A = n^2 + 2 is not divisible by 4. ( Algebratically )

Answer 4

• ( If n is odd, n = 2m + 1 )
• ( 2m + 1 )^2 + 2
• 4m^2 + 4m + 3
• 4m ( m + 1 ) + 3, the number is 3 more than a multiple of 4, so not divisible by 3
• ( If n is even, n = 2m )
• ( 2m )^2 + 2
• 4m^2 + 2, the number is 2 more than a multiple of 4, so not divisible by 4
• Hence if n is an integer, then A = n^2 + 2 is not divisible by 4.

Question 5

Suppose x and y are odd positive integers less than 7.

Prove that their sum is divided by 2.

Answer 5

• Numbers can be 1, 3 and 5
• combinations can be 1 and 3, 3 and 5, 5 and 1
• 1 + 3 = 4 / 2 = 2, the sum of 1 and 3 is divisible by 2
• 3 + 5 = 8 / 2 = 4, the sum of 3 and 5 is divisible by 2
• 5 + 1 = 6 / 2 = 3, the sum of 5 and 1 is divisible by 2
• Hence, if x and y are odd numbers less than 7, the sum of them can be divisible by 2

Question 6

Prove that for every integer n, n( n + 1 ) is even.

Answer 6

• n can either be odd or even
• n = 2n or 2n + 1
• 2n ( 2n + 1 )
• 4n^2 + 2n
• 2n ( 2n + 1 ), when n is even, it is a multiple of 2 which is an even number
• 2n + 1 ( 2n + 1 + 1 )
• 2n + 1 ( 2n + 2 )
• 4n^2 + 4n + 2n + 2
• 4n^2 + 6n + 2
• 2 ( 2n^2 + 3n + 1 ), when n is odd, it is a multiple of 2 which is an even number
• Hence for every integer of n, n( n+ 1 ) is even

Question 7

Prove that there are only two distinct triangles with sides of integer length that have a perimeter of 11.

Answer 7

• ( First of all we need to bring cases of three different sides which add up to 11 )
• ( We can start with the first number being 1 )
• 1, 2, 8
• 1, 3, 7
• 1, 4, 6
• 1, 5, 5
• ( Now we can start thinking about sides that begin with 2 )
• 2, 3, 6
• 2, 4, 5
• 2, 5, 4 ( remember third side cannot be smaller than the second side ) ( So this value isn’t included )
• ( Now we should think about sides that begin with 3 )
• 3, 4, 4
• ( These are all the possible different sides for the triangle )
• ( However, for the sides to be a triangle, any two sides must sum up to be more than the third side )
• ( So for each, we identify if they are triangles or not )
• 1, 2 ,8 ( 1 + 2 = 3 < 8, so cannot be a triangle, two sides sum up to be less than the third )
• 1, 3, 7 ( 1 + 3 = 4 < 7, so cannot be a triangle, two sides sum up to be less than the third )
• 1 , 4, 6 ( 1 + 4 = 5 < 6, so cannot be a triangle, two sides sum up to be less than the third )
• 1, 5, 5 ( 1 + 5 = 6 > 5, so can be a triangle, two sides sum up to be more than the third side )
• 2, 3, 6 ( 2 + 3 = 5 < 6, so cannot be a triangle, two sides sum up to be less than the third )
• 2, 4, 5 ( 2 + 4 = 6 > 5, so can be a triangle, two sides sum up to be more than the third side )
• 3, 4 , 4 ( 3 + 4 = 7 > 4, so can be a triangle, two sides sum up to be more than the third side )
• So { 1, 5, 5 }, { 2, 4, 5 } and { 3, 4 ,4 } are the only set of numbers that give three distinct triangles with sides of integer length that have a perimeter of 11.

( I don’t know where they got two from…????? )

Question 8

*Show that n^3 - 1 = ( n - 1 ) ( n^2 + n + 1 )

Don’t understand

Question 9

*Prove that n^7 - n is divisible by 7 for all positive values of n.

( Knowing that n^3 - 1 = ( n - 1 ) ( n^2 + n + 1 ) )

Question 10

Prove that the remainder, when an integer n is divided by 3, is the same as the remainder when n^3 is divided by 3.

Answer 10

There are three cases to consider:

• n = 3m
• n = 3m + 1
• n = 3m + 2
• ( Where m is an integer )
• n = 3m, n^3 = ( 3m )^3 = 27m^3, which is a multiple of 3
• n = 3m + 1, n^3 = ( 3m + 1 )^3 = 27m^3 + 27m^2 + 9m + 1
• n^3 = 3 ( 9m^3 + 9m^2 + 3m ) + 1
• ( The remainder of n and n^3 is 1 when they are both divided by 3 )
• n = 3m + 2, n^3 = ( 3m + 2 )^3 = 27m^3 + 54m^2 + 36m + 8
• n^3 = 3 ( 9m^3 + 18m^2 + 12m + 2 ) + 2
• ( The remainder of n and n^3 is 2 when they are both divided by 3 )
• Hence the remainder, when an integer n is divided by 3, is the same as the remainder when n^3 is divided by 3.