Today's lecture was so interesting, I answered one of Paul's questions!

In other news, the Micro test is still not marked; I have worked out what full verifiability is but not how to recognise it (to see my problem, compare the formal definition of differentiability with what you do in your mind to determine differentiability); and I'm truly intrigued by the fact that 15^{x} = 15 (mod 35) for *any integer x*.

## 3 comments:

Counting number, perhaps :-P

How about:

3^x mod 6

4^x mod 6

5^x mod 10

6^x mod 10

7^x mod 14

8^x mod 14

9^x mod 18

10^x mod 18

11^x mod 22

12^x mod 22

13^x mod 26

14^x mod 26

15^x mod 30

Actually I wasn't expecting that Pattern!!

And it's not the smallest numbers once you get on a bit. For example 15 will work with 21, 30, 35, 42, 70, 105.

Hey, that's pretty cool.

All is revealed, sort of, by Theorem 15.7 of my math notes. Fermat's Little Theorem accounts for some of the phenomenon; I still need to think about the rest.

Here's what I did (don't need no stinkin' theorems).

Thinking inductively, all you have to do is find a number d such that n^2 mod d = n. Once you do that, if you multiply by n again all you're really doing is multiplying the original remainder and then modding it back down.

The obvious candidate for d is n^2 - n. n^2 mod n^2 is 0, so n^2 mod (n^2 - n) is clearly n.

Then it's a matter of "do we have the smallest number that will work?". Take the factors of d and find the smallest one that is bigger than n.

Actually I don't see any reason that there might not be smaller numbers that work somewhere in the factors of, say n^2 - 2n. But I haven't tried that.

## Post a Comment

You can use $\LaTeX$ here if you like. Enclose it in "$" or "\[" as if you were using your favourite editor.

Note: Only a member of this blog may post a comment.