Linked Questions

98
votes
9answers
13k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
88
votes
9answers
5k views

Divisibility by 7 rule, and Congruence Arithmetic Laws

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = (...
8
votes
4answers
3k views

Find the last two digits of $9^{{9}^{9}}$ [duplicate]

I have to find the last two decimal digits of the number $9^{{9}^{9}}$. That's what I did: $$m=100 , \phi(m)=40, a=9$$ $$(100,9)=1, \text{ so from Euler's theorem,we have :} 9^{40} \equiv 1 \pmod{...
7
votes
2answers
890 views

Fermat's Little Theorem and Euler's Theorem

I'm having trouble understanding clever applications of Fermat's Little Theorem and its generalization, Euler's Theorem. I already understand the derivation of both, but I can't think of ways to use ...
7
votes
2answers
9k views

Modulus of Fraction

I just want to confirm I am doing this problem correctly. The problem asks to compute without a calculator: $$ 3 * \frac{2}{5} \pmod 7 $$ The way I am solving the problem: $$ 3 * \frac{2}{5} \bmod 7 \...
6
votes
5answers
812 views

Calculate $121^{199} \mod 300$

Using Fermat's little theorem I proved that $$121^{199} = 121^{39} \mod 300$$ (as $\phi(300)$ is $80$) but I don't think I can leave it like this. My question being how can I solve $121^{39}\...
6
votes
3answers
2k views

Mod of numbers with large exponents

I've read about Fermat's little theorem and generally how congruence works. But I can't figure out how to work out these two: $13^{100} \bmod 7$ $7^{100} \bmod 13$ I've also heard of this formula: $...
1
vote
4answers
932 views

Find the last two digits of $9^{9^{9}}$ [duplicate]

I want to find the last two digits of $9^{9^9}$ or $9^{81}$. I tried using Euler's theorem but I can't make anything of it. Any hint or a guide? Thanks!
1
vote
0answers
178 views

How to find the last two digits of $9^{9^{9^9}}$? [duplicate]

Possible Duplicate: The last two digits of $9^{9^9}$ How to find the last two digits of $9^{9^{9^9}}$ (a power tower of 4 $9$'s) ? Is there any special approach to these kind of problems?
0
votes
2answers
152 views

Clarification needed on finding last two digits of $9^{9^9}$

I stumbled across this problem here. In the answer given by the user Gone, I don't see how he makes use of the second line in the last line. Could someone explain why he calculated $9^{10}$ via ...
-1
votes
1answer
97 views

Finding the last two digits of $9^{9^{9^{…{^9}}}}$ (nine 9s) [duplicate]

I'm continuing on my journey learning about modular arithmetic and got confused with this question: Find the last two digits of $9^{9^{9^{…{^9}}}}$ (nine 9s). The phi function is supposed to be used ...