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$.

898 questions
11k 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, ...
13k views

Why is $a^n - b^n$ divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ $-$...
5k views

Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...
4k views

12k views

Find the last two digits of $7^{81} ?$

I came across the following problem and do not know how to tackle it. Find the last two digits of $7^{81} ?$ Can someone point me in the right direction? Thanks in advance for your time.
3k 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 ...
2k views

The last two digits of $9^{9^9}$

I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$. How do I proceed further?
2k views

Not understanding Simple Modulus Congruency

Hi this is my first time posting on here... so please bear with me :P I was just wondering how I can solve something like this: $$25x ≡ 3 \pmod{109}.$$ If someone can give a break down on how to do ...
261 views

4k views

Show that if $a \equiv b \pmod n$, $\gcd(a,n)=\gcd(b,n)$

My problem is how to somehow relate the the gcd and congruence. I know that $(a,b) = ax + by$. I also know that $a \equiv b \pmod n$ means $n\mid a-b$. Any hints? Thanks!
165 views

$N$'s base-5 and base-6 representations, treated as base-10, yield sum $S$. For which $N$ are $S$'s rightmost two digits the same as $2N$'s?

Bernardo chooses a three-digit positive integer $N$ and writes both its base-5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two ...
3k views

Divisibility rules and congruences

Sorry if the question is old but I wasn't able to figure out the answer yet. I know that there are a lot of divisibility rules, ie: sum of digits, alternate plus and minus digits, etc... but how can ...
3k views

The last 2 digits of $7^{7^{7^7}}$

What is the calculation way to find out the last $2$ digits of $7^{7^{7^7}}$? WolframAlpha shows $...43$.
243 views

How many solutions of $\mod 63$ : $x^2=1 \pmod7$ and $x^3=1\pmod 9$ [closed]

How many solutions $\mod 63$ , we have for: $$x^2=1 \pmod 7$$ and $$x^3=1 \pmod 9$$ Need to find them also.
2k views

$1^k+2^k+3^k+…+(p-1)^k$ always a multiple of $p$? [closed]

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$1^k+2^k+3^k+...+(p-1)^k$$ always a multiple of $p$ ?
About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,... 5answers 4k views Modular Inverses I'm doing a question that states to find the inverse of$19 \pmod {141}$. So far this is what I have: Since$\gcd(19,141) = 1\$, an inverse exists to we can use the Euclidean algorithm to solve for ...
$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how. Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not $$15 = (11^2-1)/8$$ n ...