Well, not much to report since my last entry - I've spent most of the… - John C. Kirk
Jan. 14th, 2003
06:17 pm
Well, not much to report since my last entry - I've spent most of the last few days diligently studying. Consequently I haven't been very sociable (e.g. not on IRC much), but that should improve next week, once lectures start again.
Had my first exam today, which went pretty well. There were a couple of awkward questions (including one that I was really hoping they wouldn't ask, since I think it requires advanced number theory), so I dropped a few marks there, but I reckon I'm pretty much guaranteed 80%. I may get as high as 90% if the examiner is feeling charitable... I only need 70% for a Distinction, so no problem there, but it would have been nice to get a perfect score (and there is a prize for the top student in the year). Also picked up my second piece of coursework from the department - no actual mark on it, but it says "good" on the front, so I assume that means I passed. It's just a prerequisite for Friday's exam, rather than being meaningful in and of itself, so that's good enough for me. I'm now taking a brief break before I continue the revision, ready for tomorrow morning's exam (graph theory).
Which was the question ...
/me is curious
Re: Which was the question ...
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?
Re: Which was the question ...
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.