9.8 Coursework Sheet 7
Hand in your solutions in the appropriate way by Monday, 27 November 2023, 19:00.
Exercise 1
Find the general solution of each of the following congruences
- \(2x\equiv 1\mod{17}\),
- \(4x\equiv 1\mod{17}\),
- \(4x\equiv 6\mod{18}\),
- \(20x \equiv 984\mod{1984}\).
Exercise 2
(Posed by 7th century mathematician Brahmagupta) A girl was carrying a basket of (fewer than 500) eggs, and a man driving a horse hit the basket and broke all the eggs. Wishing to pay for the damage, he asked the girl how many eggs there were. The girl said she did not know, but she remembered that when she counted them by twos, there was one left over; when she counted them by threes, there were two left over; when she counted them by fours, there were three left over; when she counted them by fives, there were four left; and when she counted them by sixes, there were five left over. Finally, when she counted them by sevens, there were none left over. ‘Well,’ said the man, ‘I can tell you how many you had.’ What was his answer?
Exercise 3
Illustrate the 4-step algorithm to solve linear congruences by applying it to solve: \(8x\equiv 4 \mod{34}\). It is not enough to find the solution, you should illustrate the steps of the algorithm clearly in your working.
Exercise 4
Construct linear congruences mod \(20\) with, respectively, no solutions, just one solution and more than one solution. Can you find one with exactly \(12\) solutions? Give an example or explain why it is not possible.