# Questions tagged [modular-arithmetic]

Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $a-b$.

1,502 questions
Filter by
Sorted by
Tagged with
24k views

### Modular exponentiation by hand ($a^b\bmod c$)

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, for ...
7k views

### Mod of numbers with large exponents [modular order reduction]

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 the Congruence ...
9k views

1k views

### Solve $x^{5} \equiv 2$ mod $221\$ [Taking modular $k$'th roots if unique]

We know that $221 = 17*13$. So we can check if the system has roots to both of those equations separately, which it does: $x^{5} \equiv 2$ mod $13$ has the solution $6 + 13n$ and $x^{5} \equiv 2$ mod ...
1k views

6k views

### Sum of two squares modulo p

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How ...
5k views

### I don't understand why the inverse is this?

my question is related to matrix inverting and Hill cipher(you don't have to know what it is to help me) My teacher gave me an example. First we have a matrix (the key matrix) that multiplied by a ...
5k views

### Find the last two digits of $3^{45}$

I was wondering if there is a simpler way to find the last to digits of a power such as $3^{45}$. I reduced it modulo 100 to get the answer, which is 43. But I was curious if there was a simpler, or ...
### Prove that $6p$ is always a divisor of $ab^{p} - ba^{p}$. [closed]
Let $p> 3$ a prime number and $a, b \in \mathbb{Z}$ arbitrary. Prove that $6p \mid (ab^{p} - ba^{p})$.