Section6.6Exercises

  1. We found solutions to \(ax\equiv b\) mod (\(n\)) as congruence classes modulo \(n\). But since \(\gcd(a,n)=d\) is important here, it could be worth talking about how many congruence classes modulo \(n/d\) we have. Well, how many do we get? (If this sounds confusing, pick a specific problem and try it, then see if you get the same answer in general.)
  2. Prove that the only solutions of \(x^2\equiv x\) mod (\(p\)) are \(x=[0]\) and \(x=[1]\), if \(p\) is a prime.
  3. Try to decide for exactly which composite moduli \(n\) the previous question is true.
  4. We know that \(b\equiv c\) mod (\(n\)) implies \(ab\equiv ac\) mod (\(n\)) as well. Prove that the converse is true if \(gcd(a,n)=1\), and give a counterexample where the converse fails if \(gcd(a,n)\neq 1\).
  5. Fill in the details in the last proof of the section on simple linear congruences.
  6. Find all solutions to the following linear congruences:
    • \(18x\equiv 42\) mod (50)
    • \(15x\equiv 9\) mod (25)
    • \(6x\equiv 3\) mod (9)
    • \(980x\equiv 1540\) mod (1600)
  7. Solve the simultaneous system below. (Jones and Jones)
    • \(x\equiv 1\) mod (4)
    • \(x\equiv 2\) mod (3)
    • \(x\equiv 3\) mod (5)
  8. Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13.
  9. When eggs in a basket are removed two, three, four, five, or six at a time, there remain, respectively, one, two, three, four, or five eggs. When they are taken out seven at a time, none are left over. Find the smallest number of eggs that could have been contained in the basket. (Brahmagupta, 7th century AD)
  10. Find a problem on the internet about pirates quarreling over treasure (or monkeys over bananas) that could be solved using the CRT, and solve it.
  11. Solve the system \(4x\equiv 2\) mod (6), \(3x\equiv 5\) mod (7), \(2x\equiv 4\) mod (11).
  12. Solve the congruence \(5x\equiv 22\) mod (84).
  13. Solve the simultaneous system \(x\equiv 4\) mod (6), \(x\equiv 13\) mod (15) (Rosen). Note that this doesn't fit our pattern, but you should still be able to solve this, since there are only two.