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

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
0
votes
1 answer

The process to reduce modular congruences?

For example. given $15x\equiv 10\ (mod \ 16)$, what method would someone use to reduce this to $x \equiv 6\ (mod \ 16)$?
0
votes
3 answers

Show that if $n > 0$ is an integer, then $n^2$ is congruent to only $0,1,2$ or $4$ modulo $7$

No solution please, I just need some guidance. I've tried various approaches so far yet no prevail. I've looked at small number cases and tried to identify something interesting. Couldn't find much though. I've thought about how n can only be odd…
0
votes
1 answer

Understanding Modulus Arithmetic

I'm looking for a short text or primer (maybe max 20-30 pages) which explains the basics of modulus arithmetic and how it apply to rings. Specifically, I'm looking for a text that explains how the maps $\mathbb{Z}/p^{n+1}\mathbb{Z} \to…
0
votes
3 answers

modular arithmetic solving technique

I do know that the (mod m) in $ a\equiv b\pmod m $ is not a multiplication with b, so, the following question has really confused me: The given values are: $ a\equiv 4\ mod 13$ and $ b\equiv 9\ mod 13$, now, we find the integer 0<= c <=12…
0
votes
1 answer

modular reductions

How do I use modular reductions to compute this: 11·18·2322·13·19(mod 7)? I know the answer is 6 through 11=4mod7, 18=4mod7, 2322=5mod7, 13= -1mod7, and 19= 5mod7. I'm curious as to how you can simplify 2322=5mod7 without using a calculator.
Var98
  • 21
  • 3
0
votes
4 answers

Why $5 (\mod 7)$ is $5$?

$\frac 57$ is equal to $0.7$. Remaining is $1$. by definition, the remainder when dividing $\frac mn$ is such a number $r$ such that $0≤r
0
votes
1 answer

Calculate $12345 \pmod{11}$ and $12345\times 98765 \pmod{11}$ by hand.

I know the answers to those questions, but I'd like to know how to do them by hand.
0
votes
3 answers

Determine whether or not the following congruence has a natural number solution

Determine whether or not the following congruence has a natural number solution: $$5^x + 3 \equiv 5 \mod 100$$
0
votes
2 answers

Arithmetic of integers: divisibility, modular congruence.

Show that $70$ divide $101^{6n} - 1$ for all $n$ natural numbers. I tried to show that $101^{6n}$$ \equiv 1$ mod $70$. Thanks for all. I got it. Note that $70$ $=$ $7$.$5$.$2$ As $101^{ϕ(7)}$ $\equiv 1$ mod $7$, so $101^{6n}$ $\equiv 1$ mod $7$…
0
votes
1 answer

Number of solutions of $a \equiv b \pmod m.$

The solution set of $a \equiv b \pmod m$ is given by the set of values satisfying $b \pmod m$. The reason is that the stated congruence is actually an equality given by : $\exists k,l \in \mathbb{Z}$, s.t. $a - km = b - lm$. An easy example is :…
jiten
  • 4,524
0
votes
0 answers

Please vet proof for : If $a \equiv b \pmod n$ and if $d \mid n$, then $a \equiv b \pmod d$

If $a \equiv b \pmod n$ and if $d \mid n$, then $a \equiv b \pmod d$ It is simple as just need the divisibility based relation, $n = dk, \exists k \in \mathbb{Z}$. As, $a - ln = b - mn, \exists l,m \in \mathbb{Z}$, so for any factor $d$ of $n$…
jiten
  • 4,524
0
votes
1 answer

What is more logical, if given $a \equiv b \pmod n$; $b = a +nq$, or : $a =b +nq$

It is given here in Theorem 3.3, that if $a \equiv b \pmod n$; then $b = a +nq, \exists q \in \mathbb{Z}$. I feel that is more logical to state otherwise (i.e., $a = b + nq$), as is more close to euclidean division algorithm. The article chooses…
jiten
  • 4,524
0
votes
1 answer

Shortcut for solving $165x \equiv 100 \pmod{285}$

Shortcut for solving $165x \equiv 100 \pmod{285}$ The usual way is to check values of x, but if a shortcut is needed then it is needed to convert the equation into an equality: $165x = 100 + 285k, \exists k \in \mathbb{Z}$ This brings up a linear…
jiten
  • 4,524
0
votes
3 answers

Find $k,l$ given $x = 25 + 38k = 59 +69l, \exists k,l \in \mathbb{Z+}$

Find the smallest positive integer solution to the following system of congruence: $25\pmod{38}\equiv x \equiv 59\pmod{69}$ $x = 25 + 38k = 59 +69l, \exists k,l \in \mathbb{Z+}$ I am not having any idea to solve, and request for help The only idea…
jiten
  • 4,524
0
votes
1 answer

Which of the following values are needed for $5^{166} \mod 41$ using fast exponentiation.

Which of the following values are needed for computing $5^{166} \mod 41$ using fast exponentiation. The values given are : $$\begin{array}{c|c|} & \text{$5^{2^i} \pmod {41}$} \\ \hline \text{ 1} & 5 \\ \hline \text{2} & 25 \\ \hline \text{3}…
jiten
  • 4,524