Well, not much to report since my last entry - I've spent most of the… - John C. Kirk — LiveJournal

that you thought required number theory?

/me is curious

(Reply) (Thread)

Heh - thought that comment might get your attention :)

The idea was to design a DFA (Deterministic Finite Automaton) which would accept all numbers equal to 9 (mod 13), i.e. 9, 22, 35, etc. Leaving aside the main DFA aspect, we had a similar example in class, where it was mod 7. The solution was to construct a table of powers of 10, and their remainder after division by 7:

10^0 mod 7 = 1
10^1 mod 7 = 3
10^2 mod 7 = 2
10^3 mod 7 = 6
10^4 mod 7 = 4
10^5 mod 7 = 5
--------------
10^6 mod 7 = 1
10^7 mod 7 = 3

So, the cycle then repeats. That means you can construct a table of P/next:

P | next
--------
1 | 3
3 | 2
2 | 6
6 | 4
4 | 5
5 | 1

There is then an equation you can use to construct the DFA itself.

So, in the exam, I went through similar steps for 13:

10^0 mod 13 = 1
10^1 mod 13 = 10
10^2 mod 13 = 9
10^3 mod 13 = 12
10^4 mod 13 = 10 (actual answer is 3)
10^5 mod 13 = ?
10^6 mod 13 = ?
10^7 mod 13 = ?
10^8 mod 13 = ?
10^9 mod 13 = ?
10^10 mod 13 = ?
10^11 mod 13 = ?
10^12 mod 13 = ?

I assumed that I'd need to go through at least that many powers of 10 to get the cycle, but we weren't allowed calculators in the exam, and my mental arithmetic started to balk at this point. I was basically taking the approach of "13 goes into 52, therefore into 104, so you can multiply that by 10 various times, so to get 1000 mod 13 you say that 13 goes into 1040, then subtract 13 repeatedly until you get below 1000". When it got to 10^4 (i.e. 10,000), I said "Ok, 13 goes into 10,400. And the remainder from 100 is 9. So, if you subtract 400, your remainder is 4x9=36. So, if you're 36 under 10,000, you can add in 26 (multiple of 13), which gives you a remainder of 10". It should have been "You're 36 over, so subtract 39, which gives you a remainder of 3". So this also threw me - I was worried that I was getting a cycle already (10 showing up twice) before I'd got through all the possible remainders (in 0..12).

When we did this in class, people were calling out the remainder after each power - I don't know if they were using calculators or not. The point is, it seems ridiculous that they expect me to work out the remainder after 10 billion divided by 13 in my head! Especially given the time limit in the exam. I'm assuming that there's some trick to this, like the "if you add up all the digits of a number, then it's divisible by 9 if it adds up to a multiple of 9" thing. So, I just wrote down "Fill in the rest of the table, then use it in the calculation, but I can't do that in my head without a calculator". Admittedly, I also then screwed up the equation that uses the table, but that's my own fault for poor memory.

So, do you know any tips/tricks for this kind of thing?

(Reply) (Parent) (Thread)

The answer here is to use congruences and repeated squaring:

for example, let's calculate 10^10 mod 13.

10^2 == (-3)^2 mod 13 so 10^2 == 9 == -4 mod 13.

So 10^4 == (-4)^2 == 3 mod 13, and 10^8 == 9 == -4 mod 13.

Now 10^10=10^2 * 10^ 8, so 10^10 mod 13 == -4 * -4 == 16 == 3 mod 13.

We combine congruences by thinking of a mod b as b*N+a where N is an integer, so we have (13*N-4)*(13N-4)=13*M+3.

A brief exposition of congruences on the web can be found on Mathworld.

(Reply) (Parent) (Thread)