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
131
votes
12
answers
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 ...
- 48.6k
9
votes
3
answers
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 ...
- 241
23
votes
5
answers
9k
views
Solving linear congruences by hand: modular fractions and inverses
When I am faced with a simple linear congruence such as
$$9x \equiv 7 \pmod{13}$$
and I am working without any calculating aid handy, I tend to do something like the following:
"Notice" that adding $...
- 19.5k
11
votes
3
answers
3k
views
mod Distributive Law, factoring $\!\!\bmod\!\!:$ $\ ab\bmod ac = a(b\bmod c)$
I stumbled across this problem
Find $\,10^{\large 5^{102}}$ modulo $35$, i.e. the remainder left after it is divided by $35$
Beginning, we try to find a simplification for $10$ to get:
$$10 \equiv 3 ...
- 3,072
2
votes
2
answers
2k
views
Using gcd Bezout identity to solve linear Diophantine equations and congruences, and compute modular inverses and fractions
Isn't finding the inverse of $a$, that is, $a'$ in $aa'\equiv1\pmod{m}$ equivalent to solving the diophantine equation $aa'-mb=1$, where the unknowns are $a'$ and $b$? I have seem some answers on this ...
- 2,983
45
votes
8
answers
23k
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$ $-$...
- 557
29
votes
6
answers
51k
views
mod [= remainder] operation (and relation), name and meaning
I am trying to write the Euclidean algorithm in the following way:
$A = \lfloor A \div B \rfloor \times B + (\text{remainder of}) \: A \div B $
Now is there any symbol I can use to say "remainder ...
- 486
25
votes
2
answers
11k
views
$\bmod n\!:\ a^n \equiv 1\!\iff\! $ order of $a$ divides $n,\,$ e.g. when $\,n = \phi(m)$
How can I show that the order of an element modulo $m$ divides $\phi(m)$?
I know that if $a$ and $m$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod m$ is its ...
- 6,140
9
votes
7
answers
3k
views
Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime
I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x < b$ and $a$ and $b$ are not co-prime, ...
5
votes
2
answers
4k
views
Solving $\ge 2$ congruences by CRT = Chinese Remainder Theorem
How do I get the solution given by CRT to match another solution, e.g. the least positive?
For example say I have X = 1234. I choose ...
- 161
5
votes
5
answers
6k
views
What is the best way to solve modular arithmetic equations such as $9x \equiv 33 \pmod{43}$?
What is the best way to solve equations like the following:
$9x \equiv 33 \pmod{43}$
The only way I know would be to try all multiples of $43$ and $9$ and compare until I get $33$ for the remainder.
...
- 265
68
votes
7
answers
12k
views
Why $9$ & $11$ are special in divisibility tests using decimal digit sums? (casting out nines & elevens)
I don't know if this is a well-known fact, but I have observed that every number, no matter how large, that is equally divided by $9$, will equal $9$ if you add all the numbers it is made from until ...
- 843
64
votes
7
answers
10k
views
Compute polynomial $p(x)$ if $x^5=1,\, x\neq 1$ [reducing mod $\textit{simpler}$ multiples]
The following question was asked on a high school test, where the students were given a few minutes per question, at most:
Given that,
$$P(x)=x^{104}+x^{93}+x^{82}+x^{71}+1$$
and,
$$Q(x)=x^4+...
- 1,003
36
votes
9
answers
8k
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 ...
- 363
9
votes
2
answers
11k
views
Modular Fraction Arithmetic
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 \...
- 101
5
votes
3
answers
1k
views
CCRT = Constant case CRT: $ $ if $\,p,q\,$ are coprime then$\,x\equiv a\pmod{\! p},\ x\equiv a\pmod{\! q}\iff x\equiv a\pmod{\!pq}$
Problem: Find the units digit of $3^{100}$ using Fermat's Little Theorem (FLT).
My Attempt: By FLT we have $$3^1\equiv 1\pmod2\Rightarrow 3^4\equiv1\pmod 2$$ and $$3^4\equiv 1\pmod 5.$$ Since $\gcd(2,...
- 9,066
6
votes
3
answers
3k
views
Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$
Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$ for $p\neq q$ distinct primes.
Where can I start with this proof?
It looks similar to the Chinese Remainder Theorem, ...
- 433
2
votes
3
answers
1k
views
$a\equiv\bar a\!\pmod{\!kn}\Rightarrow a\equiv\bar a\!\pmod{\! n};\ $ $(a\bmod kn)\bmod n=a\bmod n.\ $ Congruences persist mod factors of the modulus
I noticed relation between modulo operation and number which is power of two
Example
I have to calculate $ 3431242341 \mod 2^5 $, which is $ 5 $ but it is equivalent to
$ ( 3431242341 \mod 2^9 ) \...
- 23
34
votes
5
answers
13k
views
Fibonacci divisibility properties $ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$
Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
- 555
4
votes
1
answer
2k
views
Deriving Chinese Remainder Theorem from gcd Bezout identity
We want to find the solution $x$ to the congruence system
$$\begin{align} x &\equiv r_1 \!\!\!\pmod{\!m_1}\\
x &\equiv r_2 \!\!\!\pmod{\!m_2}\end{align},\ \ {\rm where}\ \ \gcd(m_1, m_2) = 1$...
- 53
4
votes
2
answers
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 ...
- 436
3
votes
4
answers
1k
views
Solve $x^2+5x+6 \equiv 0 \pmod{\!11\cdot 17}$
Solve $x^2+5x+6 \equiv 187 \mod 187$
Solution
$$x^2+5x+6 \equiv 187 \mod 187$$
$$ (x+\frac{5}{2})^2 \equiv \frac{1}{4}$$
$$ 4(x+\frac{5}{2})^2 \equiv 1$$
$$ y:= x+\frac{5}{2} $$
$$ 4y^2 \equiv 1 \mod ...
user617243
4
votes
4
answers
1k
views
Efficiently prove $2$ generates $(\mathbb{Z}/19\mathbb{Z})^*$ [Order Testing]
So I'm first asked to compute, mod 19, the powers of 2,
$$2^{2},2^{3},2^{6},2^{9}$$
which I compute as
$$4,8,7,18$$
respectively.
I'm then asked to prove that 2 generates $(\mathbb{Z}/19\...
- 5,472
8
votes
2
answers
2k
views
$a^{\phi (n) +1} \equiv a \pmod{\! n}; $ Carmichael generalization of Fermat & Euler theorems.
I want to know a proof of an alternative form of Fermat-Euler's theorem
$$a^{\phi (n) +1} \equiv a \pmod n$$
when $a$ and $n$ are not relatively prime.
I searched some number theory books and a ...
- 632
116
votes
12
answers
41k
views
Is zero odd or even?
Some books say that even numbers start from $2$ but if you consider the number line concept, I think zero($0$) should be even because it is in between $-1$ and $+1$ (i.e in between two odd numbers). ...
- 1,319
82
votes
8
answers
216k
views
How to find the inverse modulo $m$?
For example:
$$7x \equiv 1 \pmod{31} $$
In this example, the modular inverse of $7$ with respect to $31$ is $9$. How can we find out that $9$? What are the steps that I need to do?
Update
If I have a ...
- 11.9k
5
votes
3
answers
3k
views
Find all solutions to $x^2\equiv 1\pmod {91},\ 91 = 7\cdot 13$
I split this into $x^2\equiv 1\pmod {7}$ and $x^2\equiv 1\pmod {13}$.
For $x^2\equiv 1\pmod {7}$, i did:
$$ (\pm1 )^2\equiv 1\pmod{7}$$ $$(\pm2 )^2\equiv 4\pmod{7}$$ $$(\pm3 )^2\equiv 2\pmod{7}$$ ...
- 357
5
votes
6
answers
10k
views
$\ ac≡bc\pmod{\! m}\!\iff\! a≡b\pmod {\!m/d},\ d = \gcd(c,m)\ $ [Congruence Cancellation & Division Rule]
How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then $a≡b$ $\mod \frac{m}{d}$?
Any help would be much appreciated!
user342661
17
votes
7
answers
18k
views
Prove that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime [Wilson's Theorem]
How can I show that $(n-1)!\equiv-1 \pmod{n}$ if and only if $n$ is prime?
Thanks.
- 1,817
6
votes
7
answers
4k
views
How to find last two digits of $2^{2016}$
What should the 'efficient' way of finding the last two digits of $2^{2016}$ be? The way I found them was by multiplying the powers of $2$ because $2016=1024+512+256+128+64+32$. I heard that one way ...
33
votes
5
answers
28k
views
If $n\ne 4$ is composite, then $n$ divides $(n-1)!$.
I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. ...
- 1,638
4
votes
4
answers
4k
views
Proving $\, a\equiv \bar a\Rightarrow a^b\equiv \bar a^b\, \pmod{\!n},\, $ e.g. $\,\bar a = a\bmod n$ [Congruence Power Rule]
I am working on a problem I am pretty close to solving but I can't figure out the last part. I used some algebraic manipluation to break the problem down. The problem is:
Show that the following ...
- 99
3
votes
3
answers
922
views
If $q$ is coprime to $a$ then $a\mid nq-1,\,$ so $q$ is invertible mod $a$
I think the following is true:
If $q$ is coprime to $a$ then $a\mid (nq-1)$ for some $n\in\mathbb Z$.
I have started to first reducing $n\in\mathbb Z$ to $n\in\{1,\ldots,a-1\}$ and then considering ...
- 4,001
120
votes
5
answers
172k
views
Finding a primitive root of a prime number
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?
Thanks
user27617
2
votes
6
answers
3k
views
Solving a Linear Congruence [duplicate]
I've been trying to solve the following linear congruence with not much success:
$19\equiv 21x\pmod{26}$
If anyone could point me to the solution I'd be grateful, thanks in advance
- 565
5
votes
6
answers
887
views
Prove $n-m \mid n^r - m^r\,$ [Factor Theorem, monomial case]
In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while ...
- 185
4
votes
1
answer
972
views
When a congruence system can be solved?
How to prove that a congruence system with $n$ equations can be solved if and only if all the equations can be solved two by two?
\begin{cases} x \equiv a_1 \phantom ((mod\phantom mm_1) \\ x \equiv ...
- 512
3
votes
2
answers
1k
views
Modular arithmetic: division, fractions, solving linear congruences
I want to ask a question about modular arithmetic. I know, that modular multiplicative inverse exists only if modulo and integer are relatively prime. I want to know, are there any ways of division in ...
- 55
47
votes
17
answers
97k
views
How to prove the divisibility rule for $3\, $ [casting out threes]
The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
- 583
4
votes
3
answers
934
views
How to prove that if $a\equiv b \pmod{kn}$ then $a^k\equiv b^k \pmod{k^2n}$
What I have done is this:
$a\equiv b \pmod{2n}$,
$a=b+c\times2n$, for some $c$,
$a^2=b^2+2b\times c\times2n+c^2\times2^2n^2$,
$a^2-b^2=(b\times c+c^2n)\times4n$, then
$a^2\equiv b^2\pmod{2^2n}$.
...
- 499
5
votes
3
answers
702
views
Why does the CRT formula yield a solution of a congruence system?
I understand there is a method for solving simultaneous modular equations. For example;
$$x = 2 \mod{3}$$
$$x = 3 \mod{5}$$
$$x = 2 \mod{7}$$
We find numbers equal to the product of every given modulo ...
- 19.9k
24
votes
3
answers
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 ...
- 1,937
10
votes
4
answers
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 ...
- 2,287
7
votes
4
answers
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 ...
- 103
2
votes
2
answers
691
views
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})$.
- 3,805
5
votes
3
answers
1k
views
Inverses and cancellation in modular arithmetic
I was working on a problem that resulted in the calculation:
$20 \equiv 10x \pmod{11}$.
I got the answer $x \equiv 2 \pmod{11}$ with the thought process: Since $10$ is a factor of $20$ I can rewrite $...
- 179
14
votes
2
answers
3k
views
Are integers mod n a unique factorization domain?
I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me:
Having a ring of integers mod $n$, where $n=pq$ is composite, as I understand we have ...
- 143
4
votes
2
answers
1k
views
Bijection from modular multiplication?
Say we have two integers $n$ and $k$, such that $0 < k < n$ and $gcd(n, k) = 1$.
Why is it that if we take every integer $x\in\{0,\dots, n-1\}$ and compute $k\cdot x \ (mod \ n)$, we get as ...
- 41
2
votes
2
answers
5k
views
Prove $(x+y) \text{ mod } n = ((x \text{ mod } n)+(y \text{ mod } n)) \text{ mod } n,\,$ and product analog
For all $n \in \mathbb{N}$, $n > 1$ and $x,y \in \mathbb{Z}$ prove that
\begin{equation}
(x+y) \text{ mod } n
= ((x \text{ mod } n)+(y \text{ mod } n))\text{ mod } n.
\end{equation}
Would ...
- 375
18
votes
5
answers
11k
views
Prove that $x^{2} \equiv -1 \pmod p$ has no solutions if prime $p \equiv 3 \pmod 4$.
Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$
Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$.
I know this problem has something to do with Fermat's Little ...
- 343