Base k vs Modulo k

-

Below is a message I sent to our first year students back in 2017 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, 25n is congruent to 1 (mod 8) for all positive integers n, and so 25n−1 is always divisible by 8.

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

Comments

Post a Comment

Popular posts from this blog

A rule of thumb for when to use the Ratio Test

-
The Ratio Test is a powerful test for both sequences and series of non-zero real numbers. It comes in various forms, but here is one commonly used version. Theorem (Ratio Test) Let (xn)n∈N be a sequence of non-zero real numbers. Suppose that |xn+1||xn|→L as n→∞, where L is either a non-negative real number or +∞. (a) If L>1, then |xn|→+∞ as n→+∞, the sequence (xn) is divergent, and the series ∞∑n=1xn diverges. (b) If L∈[0,1), then the series ∞∑n=1xn is absolutely convergent (and hence convergent), and the sequence (xn) converges to 0. (c) If L=1, then the Ratio Test is inconclusive , and you need to use a different test . (The Ratio Test tells you nothing in this case about the convergence or otherwise of either the sequence or the series.) Notes Here (b) does not tell you anything about the value of the sum of the series ...
Read more

An introduction to the Hahn-Banach extension theorem: Part VI

-
In this post we sketch a second proof of the Hahn-Banach Extension Theorem for continuous linear functionals on real normed spaces, this time using transfinite induction. We omit some of the details, which the reader can fill in. In particular, some of the details are similar to those involved in proving the claim made in Part V (when we obtained an upper bound for a chain). For a non-zero ordinal γ, recall that, with ordinal interval notation, we have γ=[0,γ). That is, γ is equal to the set of all ordinals which are strictly less than γ. However, we use ordinal interval notation throughout. If you prefer to use γ instead of [0,γ) that is fine, of course! Looking at the Wikipedia page on the Hahn-Banach Theorem , apparently both Hahn and Banach (independently) used transfinite induction in their proofs, rather than Zorn's Lemma. Theorem (Hahn-Banach Extension Theorem for linear functionals on normed spaces over R)  Let (E,‖⋅‖) ...
Read more

Discussion of the proof that the uniform norm really is a norm

-
In response to a request on Piazza, I gave a detailed proof that the uniform really is a norm, including some comments and warnings on possible pitfalls along the way. Here (essentially) is what I said. Let’s have a look at ‖⋅‖∞ on the bounded, real-valued functions on [0,1] (but you can also work with bounded functions on any non-empty set you like, and the same proof will work). We define ℓ∞([0,1])={f:f is a bounded, real-valued function on [0,1]}, and this is the set/space we will look at. So we set Y=ℓ∞([0,1]). Then you can check for yourselves that Y really is a vector space over R (using the usual "pointwise" operations for functions). Note that the zero element in this vector space is the constant function 0 (from [0,1] to R), which I'll denote by 0 here for clarity. (We also used Z for this function in one of the exercises.) I'll first give...
Read more