Base k vs Modulo k

Below is a message I just sent to our first year students about a connection between modular arithmetic and working in other bases. I don’t know if this helps, but somehow arithmetic modulo 10 always seems so easy to explain!

__________________________________________________________

In our introduction to modular arithmetic, I suggested a connection between “modulo k” and “base k”. For positive integers, when  working modulo 10, using decimal notation, we only care about the last decimal digit. (That is the same as the remainder when you divide by 10.)

If you work in other bases, the connection is similar: base 8 (octal) is not the same thing as modulo 8, but for positive integers, the remainder when you divide by 8 is the same as the last octal digit. For example 25 in base 10 is congruent to 1 modulo 8, and 25 base 10 is written as 31 in octal. Any power of 31 (octal) still ends in 1 (octal). Returning to decimal notation, 25^n is congruent to 1 (mod 8) for all positive integers n, and so 25^n-1 is always divisible by 8.

Exercise: for which positive integer values of n is 6^n+1 divisible by 7?

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s