Category Archives: Number theory

March 18, 2013, 8:00 am

Inside the inverted proofs class: What we did in class

3095855157_7bf2df04fa_mI’ve written about the instructional design behind the inverted transition-to-proofs course and the importance of Guided Practice in helping students get the most out of their preparation. Now it comes time to discuss what we actually did in class, having freed up all that time by having reading and viewing done outside of class. I wrote a blog post in the middle of the course describing this to some degree, but looking back on the semester gives a slightly different picture.

As I wrote before, each 50-minute class meeting was split up into a 5-minute clicker quiz over the reading and the viewing followed by a Q&A session over whatever we needed to talk about. The material for the Q&A was a combination of student questions from the Guided Practice, trends of misconceptions that I noticed in the Guided Practice responses (whether or not students brought them up), quiz questions with…

Read More

December 12, 2011, 7:45 am

Columnar transpositions: Looking at the initial cycle

Welcome to Math Monday! Each Monday here at Casting Out Nines, we feature a mathematics-themed article. Today’s is a new installment in an ongoing virtual seminar on columnar transposition ciphers.

Let’s return to our ongoing look at the columnar transposition cipher. In the last article, we introduced the notion of cycles. A cycle can be thought of as a cluster of points which are moved around in a circular nature by a permutation. All permutations — including the permutation implemented by a columnar transposition cipher — break down into a product of disjoint cycles, and we can determine the order of a permutation (the smallest nonnegative power of the permutation that returns it to the identity) by finding the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.

Since one of the main questions we are asking about CTC’s is about their order,…

Read More

November 21, 2011, 7:45 am

A formula under the hood of a columnar transposition cipher

It’s been a couple of Math Mondays since we last looked at columnar transposition ciphers, so let’s jump back in. In the last post, we learned that CTC’s are really just permutations on the set of character positions in a message. That is, a CTC is a bijective function \( \{0, 1, 2, \dots, L-1\} \rightarrow \{0, 1, 2, \dots, L-1\}\) where \(L\) is the length of the message. One of the big questions we left hanging was whether there was a systematic way of specifying that function — for example, with a formula. The answer is YES, and in this post we’re going to develop that formula.

Before we start, let me just mention again that all of the following ideas are from my paper “The cycle structure and order of the rail fence cipher”, which was published in the journal Cryptologia. However, the formula you’re about to see here is a newer (and I think improved) version of the one in the…

Read More

September 19, 2011, 8:00 am

Math Monday: What is casting out nines?

http://www.flickr.com/photos/artnoose/

Last week in this post, I asked for requests for math topics you’d like to read about. One person wrote in and asked:

Why don’t you enlighten us about the name “Casting Out Nines?” I learned a system in grade school with the same name –it was a way of checking multiplication and long division answers. Long before calculators.

A review please?

OK then. Casting out nines is an old-fashioned method of checking for errors in basic arithmetic problems (addition and subtraction too, not just multiplication and division). Here’s how it works, using addition as an example.

Let’s suppose I’m trying to add 32189 to 87011. I get a sum of 119200. But did I make a mistake? Do the following to check:

  1. Take the first number, 32189, and remove — “cast out” — any 9′s…

Read More