Programming tasks

Questions requiring creation of a program or algorithm to find solutions to number theory problems like Pythagorean triples or Wilson primes.

4 questions · Challenging +1.6

Sort by: Default | Easiest first | Hardest first
OCR MEI Further Pure with Technology 2019 June Q2
20 marks Challenging +1.8
2
  1. Prove that if \(x\) and \(y\) are integers which satisfy \(x ^ { 2 } - 2 y ^ { 2 } = 1\), then \(x\) is odd and \(y\) is even.
  2. Create a program to find, for a fixed positive integer \(s\), all the positive integer solutions \(( x , y )\) to the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) where \(x \leqslant s\) and \(y \leqslant s\). Write out your program in the Printed Answer Booklet.
  3. Use your program to find all the positive integer solutions \(( x , y )\) to the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) where \(x \leqslant 600\) and \(y \leqslant 600\). Give the solutions in ascending order of the value of \(x\).
  4. By writing the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) in the form \(( x + \sqrt { 2 } y ) ( x - \sqrt { 2 } y ) = 1\) show how the first solution (the one with the lowest value of \(x\) ) in your answer to part (c) can be used to generate the other solutions you found in part (c).
  5. What can you deduce about the number of positive integer solutions \(( x , y )\) to the equation \(x ^ { 2 } - 2 y ^ { 2 } = 1\) ? In the remainder of this question \(T _ { m }\) is the \(m ^ { \text {th } }\) triangular number, the sum of the first \(m\) positive integers, so that \(T _ { m } = \frac { m ( m + 1 ) } { 2 }\).
  6. Create a program to find, for a fixed positive integer \(t\), all pairs of positive integers \(m\) and \(n\) which satisfy \(T _ { m } = n ^ { 2 }\) where \(m \leqslant t\) and \(n \leqslant t\). Write out your program in the Printed Answer Booklet.
  7. Use your program to find all pairs of positive integers \(m\) and \(n\) which satisfy \(T _ { m } = n ^ { 2 }\) where \(m \leqslant 300\) and \(n \leqslant 300\). Give the pairs in ascending order of the value of \(m\).
  8. By comparing your answers to part (c) and part (g), or otherwise, prove that there are infinitely many triangular numbers which are perfect squares.
OCR MEI Further Pure with Technology 2023 June Q2
11 marks Challenging +1.8
2 Throughout this question ( \(a , b , c\) ) is a Pythagorean triple with the positive integers \(a , b , c\) ordered such that \(a \leqslant b \leqslant c\).
  1. Show that \(\mathrm { a } ^ { 2 } = \mathrm { b } + \mathrm { c }\) if and only if \(\mathrm { c } = \mathrm { b } + 1\).
  2. Create a program to find all the Pythagorean triples ( \(a , b , c\) ) such that \(\mathrm { a } ^ { 2 } = \mathrm { b } + \mathrm { c }\) and \(c \leqslant 1000\). Write out your program in full in the Printed Answer Booklet.
  3. Write down the number of Pythagorean triples found by your program in (b).
  4. Prove that there is no Pythagorean triple, \(( a , b , c )\), in which \(\mathrm { b } ^ { 2 } = \mathrm { a } + \mathrm { c }\).
OCR MEI Further Pure with Technology 2023 June Q3
10 marks Challenging +1.2
3 Wilson's theorem states that an integer \(p > 1\) is prime if and only if \(( p - 1 ) ! \equiv - 1 ( \bmod p )\).
  1. Use Wilson's theorem to show that \(17 ! \equiv 1 ( \bmod 19 )\).
  2. A prime number \(p\) is called a Wilson prime if \(( p - 1 ) ! \equiv - 1 \left( \bmod p ^ { 2 } \right)\). For example, 5 is a Wilson prime because \(( 5 - 1 ) ! \equiv 24 \equiv - 1 ( \bmod 25 )\). At the time of writing all known Wilson primes are less than 1000.
    1. Create a program to find all the known Wilson primes. Write out your program in full in the Printed Answer Booklet.
    2. Use your program to find and write down all the known Wilson primes.
    3. Prove that if there is an integer solution \(m\) to the equation \(( p - 1 ) ! + 1 = m ^ { 2 }\) where \(p\) is prime, then \(p\) is a Wilson prime.
OCR MEI Further Pure with Technology 2024 June Q2
23 marks Challenging +1.8
2 Wilson's theorem states that a positive integer \(n > 1\) is prime if and only if \(( n - 1 ) ! \equiv n - 1 ( \bmod n )\).
    1. Calculate 136! (mod 137).
    2. Hence, determine if the integer 137 is prime.
    1. Create a program that uses Wilson's theorem to find all prime numbers less than or equal to \(n\).
      Write down your program in the Printed Answer Booklet.
    2. Using part (b)(i), write down all prime numbers \(x\), where \(260 \leqslant x \leqslant 300\).
    1. Explain why there is exactly one prime number congruent to \(2 ( \bmod 4 )\).
    2. Explain why no prime number is congruent to \(0 ( \bmod 4 )\).
    3. Using part (b)(ii), write down the three prime numbers \(y\), where \(260 \leqslant y \leqslant 300\), that are congruent to \(3 ( \bmod 4 )\). Label the three prime numbers in part (c)(iii) \(c _ { 1 } , c _ { 2 }\) and \(c _ { 3 }\). Define the integer \(N\) by \(N = 4 c _ { 1 } c _ { 2 } c _ { 3 } + 3\).
    4. Explain why \(N\) is not divisible by \(c _ { 1 } , c _ { 2 }\) or \(c _ { 3 }\).
    5. Write down the value of \(N ( \bmod 4 )\).
  4. The fundamental theorem of arithmetic states that every positive integer can be written uniquely as the product of powers of prime numbers. Suppose there are finitely many prime numbers congruent to \(3 ( \bmod 4 )\). Label these prime numbers \(p _ { 1 } , \ldots , \mathrm { p } _ { \mathrm { n } }\), where \(p _ { 1 } = 3\). Using the \(n - 1\) integers \(p _ { 2 } , \ldots , \mathrm { p } _ { \mathrm { n } }\), define the integer \(M\) by
    \(\mathrm { M } = 4 \mathrm { p } _ { 2 } \mathrm { p } _ { 3 } \ldots \mathrm { p } _ { \mathrm { n } } + 3\).
    1. Write down the value of \(M ( \bmod 4 )\).
    2. Explain why \(\mathrm { M } = \mathrm { q } _ { 1 } \mathrm { q } _ { 2 } \ldots \mathrm { q } _ { \mathrm { r } }\), where the integers \(q _ { 1 } , \ldots , \mathrm { q } _ { \mathrm { r } }\) are all prime.
    3. Prove that there is at least one integer \(i\), where \(1 \leqslant i \leqslant n\), such that \(q _ { i } \equiv 3 ( \bmod 4 )\).
    4. Hence, deduce that there are infinitely many prime numbers congruent to \(3 ( \bmod 4 )\).