Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A machine prints a code from to that must satisfy . Decide first whether any such code exists. Then find how many codes from to work, the smallest one and the largest one. Show the step where you divide by the gcd, and say why you may not simply cancel from and alone.
is solvable exactly when divides , and then it has solutions modulo :
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. with .
Plan. Divide by , solve modulo , and list the solutions.
Step 1. The gcd. and . So there are exactly solutions modulo .
Step 2. Divide everything by 2. . The modulus is halved too: cancelling from and alone would keep the modulus and lose a solution.
Step 3. Invert 7 modulo 19. , so .
Step 4. Solve. .
Step 5. Back to modulo 38. or .
Check. and . Both work.
Answer: codes, the smallest and the largest .
Log in to join the discussion.
Loading…