Base Conversion and Modular Arithmetic

In Session 1, we noticed that remainders play a key role in the repetition or termination of
a decimal . After a long division, if the remainder was zero, the division was finished and
the decimal terminated. If the remainder was the same number as any previous remainder,
the pattern would repeat from that point, leading to a repeating decimal.

1. Write the decimal expansion for the base-ten fraction 3/41 . How many different cycles
will there be in the decimal expansions of the fractions from 1/41 to 40/41?

2. Use long division to write the decimal expansion for the base-ten fraction 1/142857 .

Using division in other bases, it is possible to write “decimal” expansions of fractions in
other bases.

3. Write the base-ten numbers 1/3 , 1/4 , and 1/7 as “decimals” in base two and base three.
You may recall from yesterday that we cannot write “3” in base two, so the divisors
you use will have to be written appropriately.

4. Which fractions in Problem 3 terminated in which bases? Why?

5. Compare the “decimal” expansions of 1/7 in base two, in base three, in base five, in
base seven, in base ten, in base seventeen (there’s a good reason). When 1/7 repeats,
how long is its repeating pattern in each base? Is there anything unusual going on
between bases three and five? What about between bases three, ten, and seventeen?
Look carefully. You might consider using the representation of cycles we used in
Session 1.

We’ve dealt a lot now with converting fractions to decimals, but not decimals to fractions.

6. Convert the repeating decimal to a rational number (i.e., a fraction). If you are
not sure how to proceed, check the notes from Session 2.

7. Convert the “eventually repeating” decimal to a rational number. Think about
what you would multiply the decimal by to create a cancellation.

8. Convert the base-two repeating decimal to a rational number in base two. Does
this method of solution change from Problem 6 to 8? You might also consider
solving this one as a geometric series.

A slight change of direction now: we are going to start looking at just the remainders of
calculations performed in bases. For example, in base seven, 3 + 4 = 10. If we look at only
the remainders when dividing by 7, then the equation reads 3 + 4 = 0.

An arithmetic that uses remainders is referred to as a modular arithmetic. In a system
governed by remainders when dividing by 7, or modulo 7, the numbers 3, 10, 17, 24, . . . all
become the same number, and “3” would be written to represent this entire class of
numbers.

We will start with some questions about units digits in base 10, which may seen unrelated
for a short time.

9. Find the units (last) digit of the calculation 2314 × 426 + 573 × 234. Do not use a
calculator. Don’t forget about the order of operations !

10. What shortcuts did you use in Problem 9?

11. Find the last digit of (312 × 423 + 57²)(28 + 1045 × 68³). As with Problem 9, try to
do it without a calculator.

12. How can we calculate the units digit of a base-ten number by using the division
algorithm? Does this explain why units digit arithmetic is a modular arithmetic?

13. Calculate each of these in units digit arithmetic: 3 + 4, 5 + 8, 4 − 3, 2 − 7, 6 × 5,
9 × 9, 0 × 7, 4 ÷ 3.

14. Complete these addition and multiplication tables for units digit arithmetic.

Unlike ordinary arithmetic, these tables consitute ALL possible addition and
multiplication problems in this arithmetic.

15. Does order count in addition and multiplication? How can you tell just by looking
at the structure of the tables?

16. Is it true of this new addition that adding 0 doesn’t change a number? Explain,
using the table.

The “opposite” or “negative” of a number is the number that you add to it to get 0. In
ordinary arithmetic, the opposite of 4 is −4. In ordinary arithmetic, every number has an
opposite (what’s the opposite of 0?). In units digits arithmetic, the opposite of 4 is 6,
because 4 + 6 = 0.

17. Does every number have an opposite in this system? Explain. Give a rule for
determining the opposite of a number, if it has one.

18. Is it true of this new multiplication that multiplying by 1 doesn’t change a number?
Explain.

The “inverse” or “reciprocal” of a number is the number that you multiply to it to get 1.
In ordinary arithmetic, the reciprocal of 3 is 1/3 , because . In the real numbers ,
every number except 0 has a reciprocal. In units digits arithmetic, the reciprocal of 3 is 7,
because 3 × 7 = 1.

19. Does every number, other than zero, have a reciprocal in this system? Explain.

20. What’s common among all numbers that have a reciprocal? What’s common among
all numbers that don’t have a reciprocal?

21. In ordinary arithmetic, if the product of two numbers is 0, one of them must be 0. Is
that true here? Why or why not?

22. Which number in this arithmetic is the “largest”? Explain your answer, using clear
language.

The system of units digit arithmetic is the system of remainders modulo 10. This will
usually be referred to either as “mod 10” or Z₁₀. In this course, we will frequently be
working in different moduli; one purpose is to understand the differences between working
in moduli and ordinary arithmetic, thus discovering some of the underlying properties of
“ordinary” arithmetic.

Some examples: in Z₁₀, 3 × 4 = 2, since 3 × 4 = 12 in ordinary arithmetic, and 2 is the
remainder when dividing 12 by 10. In Z₇, 3 × 4 = 5. In Z₆, 3 × 4 = 0. In Z₁₆, 3 × 4 = 12.
Make a note of the last one: since we are only considering remainders now, we no longer
have to worry about place value, so there’s no need for C or other letters when writing
elements of higher mods.

If you’ve made it this far, here are some equations to solve in Z₁₀. Remember, an equation
is solved by finding all numbers in the set which make the equation true, and Z₁₀ consists
of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

23. Solve x + 6 = 2. Explain how you did it.
24. Solve 3x + 6 = 2. Explain how you did it.
25. Solve 4x + 1 = 5. Explain how you did it.
26. Solve 4x + 1 = 6. Explain how you did it.

27. What makes the solution to Problem 24 different from the solutions to 25 and 26 in
Z₁₀? Write some other equations that look similar, but have very different sets of
solutions.

28. Repeat Problems 23–26 in Z₇, in Z₁₁, in Z₁₂. How are these systems similar? How
are they different?

29. Build a table for multiplication in Z₇, then use it to answer Problems 15–19.

30. The quadratic equation x² − x = 0 has four solutions, or roots, in Z₁₀. What are
they? Why is this happening?! Why can’t this happen in ordinary arithmetic?

31. Find all solutions to x² − 6x + 8 = 0 in Z₅, in Z₁₅, in Z₁₀₅. Do the solutions you get
in Z₅ help you find solutions in Z₁₅?

Two extending questions about base conversion follow.

32. Suppose a number is written as a repeating decimal in base ten. Must it be a
repeating decimal in every other base? If yes, explain why. If no, are there any
particular bases in which it must be a repeating decimal?

33. Use the method of Problems 6–8 to find the value of What happened? Does
this reveal any assumptions inherent in converting repeating decimals to fractions?
How do geometric series apply to this problem?