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
1
vote
1 answer

Unable to solve congruence modulo arithmetic question for power of integer: $(7552)^3 \equiv ... \pmod{89}$.

I am doing simple question on congruence modulo arithmetic for power of a number, and am unable to get correct answer: $(7552)^3 \equiv ... \pmod{89}$ => $7552 \equiv (89*(100) - 1348)$$ \equiv (89*(100) -890 - (1348-890)) \implies (89*(100) -890…
jiten
  • 4,524
1
vote
1 answer

TAOCP: Section 1.2.4 -> Q 23: An example to show the law is not correct

Question: Give an example to show that Law D is not always true if $r$ is not relatively prime to $s$. Law D: If $r \perp s$, then $a \equiv b$ (modulo $rs$) if and only if $a \equiv b$ (module $r$) and $a \equiv b$ (modulo $s$). Where $r, s, a,…
Abhisek
  • 465
1
vote
1 answer

A permutation of $\mathbb{Z}_{p^d}$

Let $p$ be a prime and let $a$ and $d$ be integers such that $0\leq a
a882345
  • 13
1
vote
2 answers

Proof on linear congruence solutions

There's a proof in a section in my book on modular arithmetic I don't really understand. On linear congruences: $ax \equiv b \text{ (mod $m$)}$ Suppose that $\gcd({a,m}) = d > 1$ and $b$ is divisible by $d$. We can divide both sides of the linear…
xcrypt
  • 445
1
vote
1 answer

Discrete Math with Mod

If $b \equiv 3 \pmod{12}$, what is $8b \pmod{12}$? We can write $b=12q+3$. Then with some algebra $8b=12(8q+2)$. This is causing me problems because there is not number plus $12(8q+2)$ to tell us the remainder. Is it just zero?
1
vote
1 answer

Series of Equivalences

I got this question. If I climb $2$ stairs at a time, $1$ is left over. If I climb $3$ stairs at a time, $2$ are left over. If I climb $4$ stairs at a time, $3$ are left over. If I climb $5$ stairs at a time, $4$ are left over. If I climb…
DynamoBlaze
  • 2,781
1
vote
1 answer

Proving $(a \mod n + b \mod n)\mod k = a \mod k + b \mod k$ if $k|n$

I'm trying to show: $(a\mod n + b\mod n)\mod k= a\mod k+b\mod k$ if $k|n$ Got stuck at $((a\mod n)\mod k + (b\mod n)\mod k)\mod k=(a\mod k + b\mod k)\mod k $ I don't know how to eliminate the last $\mod k$. What am I missing?
JDizzle
  • 249
1
vote
2 answers

Is X a square in $\Bbb Z$?

I am learning about number theory and cryptography. I have a style of question that I have not seen before and I do not have any examples to go off of. The question is: Is 50 a square in $\Bbb Z^x_{71}$? Find the principal square root of it, if the…
1
vote
3 answers

Factorials in Modular Arithmetic

Is there a way to do this problem without multiplying it out or is that the easiest way to do this question? $$\begin{align}6! = 6\times5\times4\times3\times2\times1 &\equiv 720 &\mod 7 \\&\equiv 6 &\mod 7\end{align}$$
1
vote
1 answer

Concrete Mathematics: Understanding Modular Arithmetics

The theorem is There are m numbers: $$\text{0 mod m, n mod m, 2n mod m, ..., (m - 1)n mod m}$$ consist of precisely $d$ copies of the $m/d$ numbers $$0, d, 2d, ..., m - d$$ in some order, where $d = gcd(m, n)$. For example, when m = 12 and…
Abhisek
  • 465
1
vote
5 answers

How to efficiently compute $\,25^{37}\pmod{55}$?

Most efficient way to do this question? $25^{37}\cong (mod 55)$ Attempt: $25^2 \cong 20 (mod55)$ Then I don't know the best way to continue... I know how to brute force it but I'm just curious what the best way is?
1
vote
1 answer

if a is congruent to b mod n then is $ k^a $ congruent to $ k^b$ mod n

So, if we know that $a\equiv b\pmod n $ under what circumstances can we say that: $${x^a}\equiv {x^b}\pmod n$$ It seems through experimental evidence that this works for $n=10$, but does it work for all $a,b,x$ when $n=10$? What about other values…
1
vote
0 answers

Why is $(12 + 4) \mod 10$ not $6$?

In my discrete math textbook, the question is posed to us as $12$ modular addition $4$ in the context of $\mathbb{Z}_{10}$. As a hint, it says "Be careful. The answer is not $6$." I am confused by this because $ 12 + 4 = 16$ and $$ 16 \text{…
Soph
  • 21
  • 5
1
vote
3 answers

Solve $x\equiv 2\pmod 5, x\equiv 1\pmod 8, x\equiv 7\pmod 9, x\equiv -3\pmod {11}$ for $x\in\mathbb Z$.

Solve $x\equiv 2\pmod 5, x\equiv 1\pmod 8, x\equiv 7\pmod 9, x\equiv -3\pmod {11}$ for $x\in\mathbb Z$. $x\equiv a_i\pmod {m_i}$ The system of congruences has a unique solution modulo M($m_1, m_2, m_3, m_4$) $x:=…
1
vote
1 answer

Linear congruence. I need help solving $5 x − 7 \equiv 2 \pmod {17}$

I understand how to solve linear congruence if the equation is in the form of, example: $4x \equiv 5 \pmod 9$ or $x+5\equiv 2 \pmod {11}.$ My problem is, I don't know exactly what to do with the $-7$ part of the $(5x - 7)$ equation.