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

$6 \equiv 6 \pmod{7}$ or $6 \equiv -1 \pmod{7}$?

Just a quick question: Is $6 \equiv 6 \pmod{7}$ or $6 \equiv -1 \pmod{7}$? I'm just trying to figure out whether there was an error in the answer by Jazzachi in this question. Thanks.
The Pointer
  • 4,182
0
votes
1 answer

How to know if people ever meet when they are walking two different routes at the same time which intersect.

So there are two people, person A and person B, walking their own route at the same time. These routes take an arbitrary amount of time to walk and they start at an arbitrary point along this route. So if we take an intersection point p, I would…
Yadeses
  • 171
0
votes
2 answers

solving $151x − 294 \equiv 44 \pmod{7}$

I've solved normal congruence equations like $ax \equiv b \pmod{m}$ but now I am trying to solve $ 1 5 1 x − 294 \equiv44\pmod{7}$. How do I solve this one? Can I just add $294$ to both sides and solve as normal using Euclidean algorithm? I read the…
user575678
0
votes
2 answers

Solving the Congruence $20x \equiv 16 \pmod{92}$ and Giving Answer As a Congruence to the Smallest Possible Modulus

I have the following problem: Solve the congruence $20x \equiv 16 \pmod{92}$. Give your answer as (i) a congruence to the smallest possible modulus; (ii) a congruence modulo $92$. I just recently solved another congruence equations problem: Solve…
The Pointer
  • 4,182
0
votes
2 answers

How to solve for $x$: $[ (23 * 60 * 60 *1000)\mod x = 1195 ]?$

I want to solve $$(23 * 60 * 60 *1000)\mod x = 1195$$ for $x$. I understand there might be multiple solutions. I have tried plugging it into Wolfram Alpha and I get no output for $x$. How might I solve for $x$?
0
votes
1 answer

modular divsion causing difference in answer by using modulo arithmetic formula

We see that 25%2==1 but if we try to do (50/2)%2 by the formula: (a / b) % c = ((a % c) * (b^(-1) % c)) % c The first term a%c = 50%2 evaluates to zero, thus making the entire term zero. Where am i screwing?
0
votes
4 answers

Modular arithmetic power rule implications

Assume that $a \equiv b \text{ (mod m)}$, the following: $$a^n\equiv b^n \text{ (mod m)}$$ is true. However, does $a^n\equiv b^n \text{ (mod m)}$ imply that $a \equiv b \text{ (mod m)}$ is true when n is odd? If n is odd, it seems like this is…
nabu1227
  • 879
0
votes
1 answer

About Congruences of $\frac{a}{b}\mod n$

Please forgive my cursory knowledge of modular arithmetic. My question is straightforward: is there a property of modular arithmetic that simplifies $\frac{a}{b}\mod n$? I attempted using the fact that $a\cdot b\mod n \equiv ((a\mod n)\cdot(b\mod…
Tejas Rao
  • 1,890
0
votes
1 answer

How to perform modular exponentiation when residue of exponent is provided?

I have to perform the computation of $a^{b}\pmod {m}$. However, instead of providing $b$ directly, I instead know the value of $b\mod {m}$. Is it even possible to perform this calculation and if so, how do I go about it? EDIT: I know that $m$ is a…
xrisk
  • 223
0
votes
0 answers

Is there a way to find the original multiples of a modular operation?

$$7 \times 14 \mod 10 = 8$$ Is there a theorem or procedure that optimizes a way to find 7 and 14 given 8 and mod 10? Brute force is the obvious approach here, such as finding all multiples of 8, then 8 + 10, then 8 + 20, etc. but it seems like…
Levitikon
  • 271
0
votes
4 answers

Negative modulo: why is $-3$ mod $12$ equal to $9$?

I know that in general, we can represent a number $x$ as follows: $x = qn + r$ where $r$ is the remainder, $n$ is the divisor, and $q$ is the quotient. But suppose we try to calculate $-3 \div12$. An answer elsewhere on Math StackExchange suggests…
Aleksandr Hovhannisyan
  • 2,983
  • 4
  • 34
  • 59
0
votes
3 answers

Solution of a congruence

Where is my mistake please tell ,I also tried $x \equiv 1 \pmod 7$ instead of $25x \equiv 4 \pmod 7$ and $7x \equiv 4 \pmod 9$ instead of $25x \equiv 4 \pmod 9$
John757
  • 171
0
votes
1 answer

Analysis of Modular Matrix Exponentiation

I found this algorithm on Wikipedia function Matrix_ModExp(Matrix A, int b, int c) if (b == 0): return I // The identity matrix if (b mod 2 == 1): return (A * Matrix_ModExp(A, b - 1, c)) mod c Matrix D :=…
0
votes
1 answer

Solve the linear congruence $28x \equiv 63 \pmod {105}$

Solve the linear congruence $28x \equiv 63 \pmod {105} $ Now $gcd(28,105)=7$ and $7|63$ so it has solution The congruence is equivalent to $4x \equiv 9 \pmod {15}$ Now $gcd(4,15)=1$ So $4u+15v=1$ Here $u=4$, $v=-1$ Implies…
John757
  • 171
0
votes
2 answers

Mod arithmetic: What day will it be in x hours?

What day will it be in 48 hours? $$\frac{48}{24}=\frac{6}{3}(mod7)≡6∗3^{−1}(mod7)≡6∗5(mod7)≡2(mod7)$$ is the right answer. But the same technique does not work for 25…