number theory

[quaint nova]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules.
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[rancid crow]

So I take it you understand that this is all leading up to Euler's theorem, right?

[rancid crow]

Okay, so we can make a corollary to Euler's theorem.

So if gcd(a, m) = 1, then a^phi(m) == 1 (mod m). What does that make a^(phi(m) + 1) congruent to?

7e.

...no.

Not a^phi(m) + 1, a^(phi(m) + 1).

Right. And a^(phi(m) + 2)?

And a^(2phi(m) + 2)?

Why?

...what?

Right.

Therefore, in general, a^n == a^(n mod phi(m)) (mod m).

For n is a nonnegative integer, obviously.

And it's this property that lets us use modular arithmetic on tetrations.

What is the question actually asking?

...I mean... read the question.

Last 3 digits. What does that mean?

Right.

And what's phi(1000)?

Therefore it's congruent to 23^(23^23...^23 mod 400). What's phi(400)?

Therefore it's congruent to 23^(23^(23^...^23 mod 160) mod 400).

And then phi(160)?

23^(23^(23^(23^...^23 mod 64) mod 160) mod 400) mod 1000

What's phi(64)?

And then phi(32)?

Which is less than 23, so here we can start reducing. What's 23 mod 16?

So we can replace all the 23s past this point with 7s.

Maybe that doesn't generalize, but it works in this case.

And then phi(16)?

phi(8)?

What's 7 mod 4?

Replace all 7s past this point with 3s. What's phi(4)?

What's 3 mod 2?

Therefore we're done because nothing above this level contributes anything at all.

Now we evaluate from the top down, remembering to reduce by the modulus of the level we're on.

5 23s, 2 7s, 1 3, 1 1.

You really should've been writing all this down.

[rancid crow]

It's 3^1 mod 4. Which is not 3^(1 mod 4).

[rancid crow]

As it says, recall the definitions of congruence and divisibility.

I guess a good place to start would be to prove that if x is not congruent to 11 mod 12, one of the other conditions must hold.

In fact, every other modulus is a factor of 12, letting you use the rule a == b (mod nk) implies a == b (mod n).