1 Pure Mathematics

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

Question 33

A cryptographer is analyzing a security protocol that relies on the properties of prime numbers. They are required to prove the following theorem for any positive integer $n$ :

“If $n^2$ is a multiple of 7, then $n$ must be a multiple of 7.”

The start of the proof by contradiction is shown in the box below.

Assumption: There exists an integer $\in \mathbb{Z}^+$ , such that $n^2$ is a multiple of 7, and $n$ is NOT a multiple of 7.

Case 1: Let $n = 7 k + 1$ for some integer $k$ .

n^2 = (7k + 1)^2 = 49k^2 + 14k + 1 = 7(7k^2 + 2k) + 1

which is not a multiple of 7.

Case 2: Let $n = 7 k + 2$ for some integer $k$ .

n^2 = (7k + 2)^2 = 49k^2 + 28k + 4 = 7(7k^2 + 4k) + 4

which is not a multiple of 7.

Case 3: Let $n = 7 k + 3$ for some integer $k$ .

n^2 = (7k + 3)^2 = 49k^2 + 42k + 9 = 7(7k^2 + 6k + 1) + 2

which is not a multiple of 7.

Case 4: Let $n = 7 k + 4$ for some integer $k$ .

n^2 = (7k + 4)^2 = 49k^2 + 56k + 16 = 7(7k^2 + 8k + 2) + 2

which is not a multiple of 7.

A boxed start of a proof by contradiction, giving the assumption and calculations for the first four possible non-zero remainders when n is divided by 7.

Show the calculations and statements required to complete this part of the proof.

[3]

Hence prove, by contradiction, that $7\sqrt{7}$ is an irrational number.

[4]

1 Pure Mathematics

Question 33

A cryptographer is analyzing a security protocol that relies on the properties of prime numbers. They are required to prove the following theorem for any positive integer $n$ :

“If $n^2$ is a multiple of 7, then $n$ must be a multiple of 7.”

The start of the proof by contradiction is shown in the box below.

Assumption: There exists an integer $\in \mathbb{Z}^+$ , such that $n^2$ is a multiple of 7, and $n$ is NOT a multiple of 7.

Case 1: Let $n = 7 k + 1$ for some integer $k$ .

n^2 = (7k + 1)^2 = 49k^2 + 14k + 1 = 7(7k^2 + 2k) + 1

which is not a multiple of 7.

Case 2: Let $n = 7 k + 2$ for some integer $k$ .

n^2 = (7k + 2)^2 = 49k^2 + 28k + 4 = 7(7k^2 + 4k) + 4

which is not a multiple of 7.

Case 3: Let $n = 7 k + 3$ for some integer $k$ .

n^2 = (7k + 3)^2 = 49k^2 + 42k + 9 = 7(7k^2 + 6k + 1) + 2

which is not a multiple of 7.

Case 4: Let $n = 7 k + 4$ for some integer $k$ .

n^2 = (7k + 4)^2 = 49k^2 + 56k + 16 = 7(7k^2 + 8k + 2) + 2

which is not a multiple of 7.

A boxed start of a proof by contradiction, giving the assumption and calculations for the first four possible non-zero remainders when n is divided by 7.

Show the calculations and statements required to complete this part of the proof.

[3]

Hence prove, by contradiction, that $7\sqrt{7}$ is an irrational number.

[4]

1 Pure Mathematics

Question 33

1 Pure Mathematics Questions

1 Pure Mathematics

Question 33

1 Pure Mathematics Questions