re: brain teaser #64

gnome

Hurkyl,
I've been wondering, is there an analytic solution to this, or did you just write a loop with something like
if((i*37)%109==1) printf("%d",i);
?

Hurkyl

I solved the equation

37x = 1 mod 109

By computing the inverse of 37.

There's a really easy way to do this using the extended euclidean algorithm, so it could be done by hand, but I used a function I wrote for my TI-89 a while back for raising numbers to high powers given a modulus, using the fact that:

x^108 = 1 (mod 109) (for x relatively prime to 109)
so
37^(-1) = 37^107 (mod 109)

gnome

Sorry, I can't figure out what you did.

How do you determine that? It seems to be true in some cases, i.e
2^2 = 1 mod 3
2^4 = 1 mod 5
2^6 = 1 mod 7

but 2^8 = 4 mod 9

That, I don't understand at all.

Please explain.

Hurkyl

Sorry, I was in a hurry this morning.


The general result is the following: if gcd(a, n) = 1, then:

a^φ(n) = 1 (mod n)

Where φ(n) is the Euler-phi function; the number of integers in the range [1, n] that are relatively prime to n.


The special case for n prime is Fermat's Little Theorem. If n is prime, then φ(n) = n - 1, and we have that x^(n-1) = 1 (mod n) for any x relatively prime to n.


So we know that 37^108 = 1 (mod 109), since 109 is prime. Using this fact, can you tell me a number, y, with the property that 37y = 1 (mod 109)?

gnome

[g)]

I should probably heed the words of the wise man who said, "When you find that you have dug yourself into a hole, stop digging."

I've spent an hour or so reading about the phi function, & maybe I have a crude understanding of it.

But to answer your question:
y = 37^107 has that property but I don't see where that leads.

...I just rolled back to your previous post, & look at that -- there I see 37^107 ... but I'm still not getting it, & I have to "knock off" for now. I'll give it some more thought tomorrow. Any more clues?

Thanks.

Hurkyl

Well, we want to solve the equation

37 x = 1 (mod 109)

And now we know the solution is x = 37^107.

gnome

Duh!

Thanks Hurkyl.

I kinda got lost in the woods, trying to understand Eric Weisstein's explanation of the Euler totient function, as he calls it, & lost sight of what we were trying to solve.

So, if I understand correctly now, that's a really neat solution that'll work for any prime number of skyscrapers assuming your machine can handle really big integers. Ubasic comes in very handy for this. [:)]

But what if the number of skyscrapers was non-prime, or the puzzle called for some remainder other than 1? Would there be any way to adapt this approach?

NateTG

Well, there's a pretty easy approach that doesn't require fermat's little theorem:
37*3=111 ≡ 2 mod 109
2*55=110 ≡ 1 mod 109
so
3*55=165 ≡ 56 mod 109 is 37 inverse.

There's a bit of fiddling, but this type of technique will get you n inverse in log₂n steps regardless of the modulus.

gnome

I'm glad you posted that, Nate, because now I realize that I still don't really understand Hurkyl's approach (or your's).

I don't see why he was looking for 37^107, or how that got him to 56, or how you are getting to 56.

I finally figured out that what you and he are referring to when you say that 56 is 37 inverse (I hope) is that 56 is the number which, when multiplied by 37 and then divided by 109 leaves a remainder of 1. But I don't see how you are getting to that.

About all I've gotten out of this so far is a vague understanding of the Euler phi-function.

Sorry to be so dense.

Hurkyl

The phi function is definitely worth learning! However, my approach to solving this equation is definitely not the most practical; the only reason I used it was because it was the first method that popped into my head and I had the tools available to compute it.

I imagine that Nate's approach is closely related to the approach using the extended euclidean algorithm. When you use the extended euclidean algorithm to compute gcd(m, n), it gives you integers u and v such that:

um + vn = gcd(m, n)

If we are given that x is relatively prime to n, we know that gcd(x, n) = 1. If we apply the extended euclidean algorithm, we get integers u and v such that:

ux + vn = 1

Now, if we reduce this equation mod n, we get

ux = 1 (mod n)

So this is how we can compute inverses with the extended euclidean algorithm.



The trick to the extended euclidean algorithm is to remember the steps you performed while computing the gcd. Allow me to demonstrate:

We start wtih gcd(37, 109)

The first step of the euclidean algorithm for computing this gcd is to subtract from 109 a multiple of 37, preferably the largest multiple of 37 that is less than 109, which is 74. So, we have:

gcd(37, 109) = gcd(37, 109 - 74) = gcd(37, 35)

But we need to keep track of the operations we performed, so we also note that:

35 = 109 - 2 * 37

Then we subtract 35 from the left side to get:

gcd(37, 35) = gcd(2, 35)

And we note that

2 = 37 - 35 = 37 - (109 - 2 * 37) = 37 - 109 + 2 * 37 = 3 * 37 - 109

Finally, we subract 34 fom 35 to get:

gcd(2, 35) = gcd(2, 1) = 1

And we note that

1 = 35 - 2 * 17 = (109 - 2 * 37) - 17 * (3 * 37 - 109) = 18 * 109 - 53 * 37

So now we know that:

1 = (-53) * 37 = 56 * 37 (mod 109)


There are much better ways of doing this bookkeeping, but I just wanted to demonstrate the idea.

gnome

S**t! This is like Pandora's box. Each step of the way something else pops up that I have to learn to understand the previous step. Recursive learning? It's wonderful of you guys to try to give me this intro, but I don't think I have time to teach myself number theory & keep up with the courses I'm actually taking now.

Thanks, anyway. I'll return to this topic as time permits.

By the way, in what course & at what level are such topics normally covered? It seems we barely scratched at the surface in the Discrete Structures course I took last year.