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

Prove that if $[a] + [b] \equiv [a] + [c] \pmod n$, then $[b] \equiv [c] \pmod n$.

The question is very clear that we are dealing with classes. Does that change anything in this case? This was an unsolved example for class and I feel it's unusual that I don't know how to begin.
grayQuant
  • 2,619
1
vote
1 answer

Shouldn't remainder be always less than divisor?

When dealing with negative modulo such as 7 (mod -5) = -3 is it not necessary that remainder be less than divisor? I thought modulo should always be positive but the calculator certainly seem to have no problem with negative modulo. Does the rules…
user615531
1
vote
4 answers

Trying to find a modulo for $2^{24}$

I was trying to figure out which modulo $n$ would make $2^{24}$ congruent to $1 \bmod n$. One answer is $241$, and I wonder if there is a good way to find it. I tried to use Fermat's little theorem or Chinese Remainder theorem, but $24$ is not a…
1
vote
4 answers

Result of mod division

I am trying to understand the result of modulo division aka multiplication with the multiplicative inverse. When I try (using a computer program) the following example the result makes sense: $$ 6 \times 3^{-1} \equiv 2\pmod{13} $$ But I cannot…
savx2
  • 125
1
vote
1 answer

Equations With Two Linear Congruences

Is there a known way to isolate a variable when the equation has two linear congruences each containing the variable? $$200=\left(\frac{x}{4}-(x \mod 17)+\frac{3}{4} \right)\cdot 3 \cdot \left(\frac{x}{3}-(x \mod 17)+\frac{4}{3} \right) \cdot 7$$
Perry
  • 11
1
vote
1 answer

Proof involving congruence of integers with a biconditional

For any set S = {a, a+1, ..., a+5} where 6|a, 24|($x^2$ - $y^2$) for distinct odd integer x and y in set S if and only if one of x and y is congruent to 1 modulo 6 and the other is congruent to 5 modulo 6 I think I have one half of the biconditional…
T. Joe
  • 31
  • 3
1
vote
1 answer

finding m for which modular arithmetic statement is true

Suppose for all $n\in\mathbb Z$, we have $(x + 4n)^2\equiv x^2\bmod m$. Find all $m\in\mathbb N$ for which this is a true statement. I have no idea how to go about finding m. I tried to use the fact that $(x+4n)^2 - x^2$ should be divisible by m,…
1
vote
0 answers

Period finding: Why x^r (mod N) is a periodic function?

If I take an example, I can observe that it is the case, but I am not able to understand why an exponentially rising function x^r would hit say x^r (mod N) periodically. r is a variable here, and x and N are given inputs. Example: N = 21, x = 2,…
shul
  • 109
  • 9
1
vote
1 answer

In modular arithmetic, why is (x mod n)^y mod n == x^y mod n?

Why is (x mod n)^y mod n == x^y mod n? It seems to me like there is a property in modular arithmetic that explains why, does anyone have a simple way of explaining it?
J. Doe
  • 11
1
vote
3 answers

How can one calculate $342342^{1001}$ mod $5$?

How can one calculate $342343^2$ mod $3$? I know that the answer is $1$. And $342342^{1001}$ mod $5$. I know that $ 3^0 \mod 5 = 1 \\ 3^1 \mod 5 = 3 \\ 3^2 \mod 5 = 4 \\ 3^3 \mod 5 = 2 \\\\ 3^4 \mod 5 = 1 \\ 3^5 \mod 5 = 3 \\ 3^6 \mod 5 = 4 \\ $ So…
user607280
1
vote
2 answers

What is the value of $43^{1234567890} \mod 22$?

How can one find out the value of $43^{1234567890} \mod 22\;?$ Can I just say that because $123456890$ is an even number I can calculate $43^2 \mod 22$, which is $1$?
1
vote
3 answers

Proof Verification: If $a\in \mathbb{Z}$, then $a^3≡a \pmod{3}$.

So, I understand that congruence equation can be written as $a^3 -a = 3k$ ,$k\in \mathbb{Z}$. I also understand that this can be written as $a(a^2 - 1) = 3k$, which can be simplified further to show the multiplication of $3$ consecutive integers.…
Logan
  • 21
  • 1
1
vote
1 answer

simplyfying a mathematical expression

How to calculate the value of below expression where $M$ is 1000000007 (prime) and $N$ can be any large number $\le 1000$? \[\frac{N!}{(N/2)!(N/2)!} \mathbin{\%} M\] It is possible to simplify it like \[\frac{(N/2 + 1)(N/2 + 2)\cdots…
g4ur4v
  • 169
1
vote
3 answers

How to solve $(x \mod 7) - (x \mod 8) = 5$?

I'm trying to solve $(x \mod 7) - (x \mod 8) = 5$ but no idea where to start. Help appreciated!
1
vote
1 answer

Simultaneous congruence with a coefficient for x

Im trying to solve the following Simultaneous congruence. $2x ≡ 3(mod\ 5) $ $3x ≡ 2(mod\ 4)$ $4x ≡ 3(mod\ 9) $ by Chinese remainder theorem $x$ = $B_1c_1x_1 \ + \ B_2c_2x_2 \ + B_3c_3x_3 \ $ Where $c_1 = 3$ $c_2 = 2 $ $c_3 = 3$ $B_1 = 2$x$3 $…