Number Theory Worksheet 3 – Modular Arithmetic

  1. If can be any natural number:
  2. What are the possible remainders when is divided by 3?
  3. For what powers of do we obtain the same residues as in (a)?
  4. Suppose that was expressed in the form , for positive integers . For which is this possible?
  5. Determine the arithmetic sequence of the following number of primes, such that the last term in the sequence is the smallest possible value: (for example, for 3 primes, the arithmetic sequence would be 3, 5, 7, and for 4 primes, the arithmetic sequence would be 5, 11, 17, 23)
  6. 5 primes.
  7. 6 primes.
  8. [Source: Based on a UKMT Mentoring question] Suppose that where and are integers. By considering possible residues for the RHS modulo-10 and similarly the residues on the LHS modulo-10 as increases, find all integer solutions.
  9. Give the form of all numbers which leave a remainder of 1 when divided by any of 2, 3 or 5.
  10. [Source: UKMT Mentoring] Find all values for which is prime, where is prime (Hint: as per the lecture slides, consider different moduli).
  11. Give the form of all integers such that is divisible by 7. (Hint: consider the residues of and as increases)

Number Theory Worksheet 3 – Modular Arithmetic - ANSWERS

  1. If can be any natural number: (a) What are the possible remainders when is divided by 3? (b) For what powers of do we obtain the same residues?
    If then . We’ll obtain the same residues for any even power, because if then be laws of modular arithmetic, , and represents any even power of .
  2. Suppose that was expressed in the form , for positive integers . For which is this possible?
    The possible remainders of modulo-7 are 0, 1, 1, 6, 1, 6, 6. And the remainder of in modulo-7 is obviously . Thus we require that .
  3. Determine the arithmetic sequence of the following number of primes, such that the last term in the sequence is the smallest possible value: (for example, for 3 primes, the arithmetic sequence would be 3, 5, 7, and for 4 primes, the arithmetic sequence would be 5, 11, 17, 23)
  4. 5 primes.
    Using the principles from the slides, our difference has to be divisible by 2 otherwise we’d have an even number (not prime!) every other number, and we’d have a number divisible by 3 every third number if the difference wasn’t divisible by 3 (recall that we see all possible residues modulo-3 each 3 numbers if the difference is coprime to 3, and since 3 is prime, it will be coprime with any number that is not a multiple of itself). If the first number was 5 (which is prime), then we wouldn’t need the difference to be divisible by 5 because the next number divisible by 5 wouldn’t be until 5 numbers later in the sequence (i.e. beyond the end of the list). So the difference has to be divisible by at least if the first number is 5, and be divisible by if the first number isn’t 5.
    And indeed this works: .
  5. 6 primes.
    By the same reasoning as above, the difference must be divisible by 2, 3 and 5, and thus divisible by 30. The first term then can’t be 2, 3 or 5. But making the first term 7 and the difference 30 works:
    .
  6. Suppose that where and are integers. By considering possible residues for the RHS modulo-10 and similarly the residues on the LHS modulo-10 as increases, find all integer solutions.
    is divisible by 10 when , i.e. .
    The possible residues of square number modulo-10 are . Since the residue can’t be 3, the equation has no solutions when . All that remains is to check :
    (which is a square, so is a solution)
    (which is not square)
    (which is square, so is a solution)
  7. Give the form of all numbers which leave a remainder of 1 when divided by any of 2, 3 or 5.
    Since 2, 3 and 5, the lowest common multiple of these numbers is . Clearly a number is divisible by 2, 3 and 5 if and only if it is a multiple of 30. Thus a number of the form where will give a remainder of 1.
  8. Find all values for which is prime, where is prime (Hint: as per the lecture slides, consider different moduli).
    In modulo-3, the possible residues of are 0, 1 and 2. But we can exclude the 0 case because otherwise would be divisible by 3 and thus not prime. The possible residues of are 1, 1, and thus 0, 0 once we add the 14. These are both divisible by 3. Thus there are no values for which is prime.
  9. Give the form of all integers such that is divisible by 7.
    Let’s work in modulo 7, so that we require . Trying the first few values of gives us , where we can clearly see with have a cycle every 3 digits (the reason is because if , then , so that the remainder is 1 whenever the power is multiple of 3). As we similarly consider , we get the residues, as increases. Since one cycles every 3 values and the other every 7 values, the two combined cycle every 21 (i.e. the Lowest Common Multiple of 3 and 7). Writing out these residues, we find that we get a remainder of 0 overall when . Thus the form of is , etc.