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
2
votes
3 answers

Solve system of congruences $k^2 + l^2 \equiv 0 \mod 17 \wedge k^3+l^3 \equiv 0 \mod 17$

Solve system of congruences $$k^2 + l^2 \equiv 0 \mod 17 \wedge k^3+l^3 \equiv 0 \mod 17$$ Is there any faster way to solve that congurence than looking at table and finding such pairs of $i$ that in both cases it gives $0$? When we have this…
user617243
2
votes
4 answers

How do I find a number x if I know that x mod a = b, x mod c = d and so on?

The actual question is if there is a number x, and x mod 19 = 1, x mod 12 = 1 and x mod 17 = 14, what is the number? I can solve this by using kinda brute force way. 19 * 12 * n + 1 = x, n is an integer, I tried from n = 1 until when n = 14, x mod…
geliba187
  • 131
2
votes
1 answer

Prove that: (a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n

(a * b)$^{x}$ mod n = ((a$^{x}$ mod n) * (b$^{x}$ mod n)) mod n Can anyone give me some tips to prove the above equation? Thanks.
2
votes
2 answers

Finding x in $a^{x} \bmod b = c$ when values a,b, and c are known?

If values $a$, $b$, and $c$ are known, is there an efficient way to find $x$ in the equation: $a^{x} \bmod b = c$? E.g. finding $x$ in $128^{x}\bmod 209 = 39$.
2
votes
1 answer

Modular Inverse using Extended Euclidean Algorithm

I am trying to find the modular inverse for $(n+1)\pmod {n^2}$ using EEA and I end up getting $1-n$ as the modular inverse. But, I want the inverse to be a positive number since its modular arithmetic. Example: For $n = 3$, the modular inverse of $4…
Nik
  • 21
2
votes
4 answers

Fastest way to solve congruency equation

I've developed an equation that solves a problem I'm working on, but the only way I know how to solve it is by incrementally trying values of $n$ from $1 \to \infty$ until I arrive at the solution. I'm hoping someone can point me to some relevant…
2
votes
3 answers

How do I solve this congruency?

I have this congruence relation: 2013 ≡ 1012 (mod m) I am supposed to find all m in the natural system.
0xFF
  • 319
2
votes
2 answers

Integer Congruence Explanation

Edit: I don't think I've expressed myself very well. This is another way of putting my question. We can say two integers, a and b, are congruent mod m (where m is a natural number) if both numbers divided by m produce the same remainder. In other…
2
votes
1 answer

Why $(a^n X_i)\bmod m = ((a^n \bmod m) X_i) \bmod m$

I've seen similar posts here asking why $(ab)\bmod m = (a \bmod m)( b \bmod m)$, but none of them really answers my question or gives a detailed the mathematical proof. I know that $a\equiv b \pmod m$, $c\equiv d \pmod m)$ implies $ac\equiv bd…
PTN
  • 205
2
votes
2 answers

Last 3 digits of $3^{3^{3^3}}$

I am trying to find the last $3$ digits of $\,3^{\large 3^{3^3}}$, i.e. $\,3^{\large 3^{3^3}}\! \bmod 1000$. My idea is to apply Euler's totient function in some way, but I am unsure on how to proceed. Would someone be able to help me out?
2
votes
2 answers

Prove that $(n-1) = (n - 1)^{\beta} \pmod{n}$ when $n$ is even

Let $\alpha$, $1 \lt \alpha \lt \varphi(n)$, $\gcd(\alpha, \varphi(n)) = 1$, and $\beta \equiv \alpha^{-1} \pmod {\varphi(n)}$, where $\varphi$ is Euler's totient function. When n is even, how would I prove: $$(n-1) \equiv (n - 1)^{\beta} \pmod n$$
2
votes
1 answer

modular arithmetic question help

I have to solve $x$ given the next three equations:$x=2\mod 7$, $x=3\mod 11$ and $x=4\mod 13$. What I tried: first try to find $x$ that satisfies the first two equations. There are $a,b\in \mathbb Z$ such that $7a+11b=1$. So $x=21a+22b$. Then I…
Badshah
  • 2,976
2
votes
3 answers

Arithmetic modulo of negative number

According to Modulo of a negative number "In arithmetic modulo , we seek to express any $$ as $+$, where $$ must be a non-negative integer." This makes sense to me as we are trying to group numbers into classes from $0$ to $n$. E.g. If $n = 4$,…
mathguy
  • 927
2
votes
2 answers

$a^2 \equiv 1 \pmod{311}$

Is easy to see that we can solve $a^2 \equiv 1 \pmod{311}$ with $a \equiv 1 \pmod{311}$ and $a \equiv -1 \pmod{311}$ but how do we prove that there is no other solution without doing a table of 311 values of $a$.
2
votes
1 answer

Use WOP to prove that for integers $a, m > 0$ there are integers $q, r \ge 0$, with $r \in \{0,1,2,\dots, m-1\}$ such that $a=qm+r$

I just don't know where to start, I tried induction but that didn't work. I wrote a and m are greater than 0 and and we can say a is congruent to r(modm) but im notsure if thats correct. Any hints?
Kayy Wang
  • 87
  • 5