Linked Questions

91
votes
9answers
12k 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, ...
2
votes
1answer
1k views

Fast modulo operation [duplicate]

Possible Duplicate: calculating $a^b \!\mod c$ I have a number of form: $p^n + p$, where $p$ is a prime number and $n$ can be any large number, for example, say $10^{12}$. What is the generic ...
0
votes
1answer
88 views

calculate modular algorithm with large exponents [duplicate]

I don't know how to calculate the following modulo: $$321^{654} \mod 1013$$ Are there some easy way to do this?
4
votes
6answers
3k views

How to find remainder modulo $n$, when $n$ is a large number

I am doing RSA questions and I really could use help! Can someone show me a simple way to find $25^9 \pmod{33}$?
13
votes
3answers
4k views

Proof of this result related to Fibonacci numbers: $\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$?

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$$ Somebody has any idea how to go about proving this result? I know a proof by ...
6
votes
7answers
470 views

exponential equation

$$\sqrt{(5+2\sqrt6)^x}+\sqrt{(5-2\sqrt6)^x}=10$$ So I have squared both sides and got: $$(5-2\sqrt6)^x+(5+2\sqrt6)^x+2\sqrt{1^x}=100$$ $$(5-2\sqrt6)^x+(5+2\sqrt6)^x+2=100$$ I don't know what to do ...
2
votes
3answers
2k views

Multiplicative inverses for elements in field

How to compute multiplicative inverses for elements in any simple (not extended) finite field? I mean an algorithm which can be implemented in software.
3
votes
4answers
5k views

modulo of series summation

I have trouble with computing modulo. First, I have a summation of series like this: $$1+3^2+3^4+\cdots+3^n$$ And this is the formula which can be used to compute the series: $$S=\frac{1-3^{n+2}}{1-3^...
2
votes
3answers
77 views

Number in tens place

A number in tens place in result of $4^{2015} \cdot 9^{2016}$ is? Obviously without using calculator, though I doubt it could count with those high numbers. By tens place I mean, for example if you ...
1
vote
1answer
123 views

How to simpify the way of calculating $(a^b \bmod c) \bmod d$?

Right now I know the way to calculate $a^b \bmod c$ which is in the answer of the following question. Consider the case where $c$ is much larger than $d$. So, the result of $a^b \bmod c$ will be ...