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

Modulo Arithmetic Shortcut

Consider two numbers $x$ and $y$ such that $0
0
votes
2 answers

Solve for $a$: $ab \text{ mod } c = d$

$ab $ mod $ c = d$ $b$ and $c$ are coprime meaning that $d$ is unique in the range $0$ to $c-1$. How can I solve for a given $b, c,$ and $d$? Known that $a$ is in range $0$ to $c-1$ Real World Example: I have 10 people in a queue. If I wanted to…
LeppyR64
  • 135
  • 5
0
votes
0 answers

Calculate $a^b \mod c$

Let's say we have the expression $a^b \mkern-10mu\mod\! c$ and $b$ is really large, e.g. $37^{165}\mkern-10mu\mod 65$. How to work this out by hand? There's a way to avoid the large exponent.
Lucien
  • 115
0
votes
4 answers

how to calculate remainder of large numbers? (no calculator)

How do I calculate the remainder of $30^{29} \pmod {51}$? I cant use Fermat's little theorem since $51$ is not a prime number.
0
votes
2 answers

Modular Arithmetic: What is the solution in this case?

I can't find the multiplicative inverse of 3? This is what I did. 6/3 * (MI of 3) (mod 6) 6/3 (mod 6) A= 3 B= ? M = 6 (A * B) % M = 1 (3 * B) % 6 =1 Some body please guide me how can I solve this? Zulfi.
zak100
  • 177
0
votes
1 answer

Modular Arithmetic: Problem with the calculation

I am trying to solve the following: 99^7 (mod 123) = 54 Applying formula: =(99 * 99^2 * 99^4) (mod 123) = [(99 mod 123) * (99 ^2 mod 123) * (99^4 mod 123)] mod 123 = [24* 75 * 75 * 75] mod 123 = 10,125,000 mod 123 = 82,317 * 123…
zak100
  • 177
0
votes
1 answer

Modular Arithmetic: Multiplicative inverse

I want to solve this question using mod arithmetic: 7/3 mod 8. Somebody told me to do it using multiplicative inverse: 7 (Multiplicative inverse of 3) mod 8 I can't find any example related to the above method. Somebody please guide me. Zulfi.
zak100
  • 177
0
votes
1 answer

Bezout lemma unique solution

If i take $a$ and $b$ such as $GCD(a,b)=1$ then for the bezout lemma the inverse of $a$ mod $b$ will exist . If $GCD(a,b)\neq 1$ there can be multiple inverses of $a$ mod $b$ or simply the inverse doesn't exist ?
AleWolf
  • 185
0
votes
1 answer

I need a modular arithmetic theorem or method

I only need a theorem or method to solve the problem (if exists). With this data and having the real value of all the data marked as letter EXCEPT "Y": X ≡ a (mod b) X ≡ c (mod d) Y ≡ a (mod b) Y ≡ c (mod d) Z ≡ a (mod b) Z ≡ c (mod d) I need to…
0
votes
2 answers

how to solve a quadratic congruence when the modulus is not square-free

$ x^2\equiv1\pmod {12} $ This factors out to $ x^2\equiv1\pmod {3 \cdot 4} $ I've tried $ x^2\equiv1\pmod 3 $ and $x^2\equiv1\pmod 4 $ doesn't seem to work; how do I deal with prime squares?
Rifat
  • 91
0
votes
1 answer

inverse modulo calculation

Let n is divisible by m, and we have to find $V=\frac{n}{m}(mod)p$... In case if we know the value of $n(mod)p$,$m(mod)p$ not n,m how can we find $V$ ????? I know we can find answer by evaluating this $(n(mod)p * m^{p-2}(mod)p)(mod)p$.but in this…
user69910
  • 151
  • 4
0
votes
0 answers

Please explain how $n!^{-1} * n \equiv (n - 1)!^{-1} \pmod{m}$

I want to find $^nC_r \bmod m$, and see this relation that $n!^{-1}\cdot n \equiv (n - 1)^{-1} \pmod{m}$, but didn't get it.
joker
  • 115
0
votes
2 answers

How to do modular arithmetic with a negative n

Playing with Python and the mod operation I encountered that (5 % -3) = -1. This is confirmed by WolframAlpha, and I have not been able to find any simple explanation for this online, mostly because all I can find about modular arithmetic uses a…
0
votes
2 answers

How to solve modulo equation?

I tried to solve the following equation system (from a 7th grade exam) in WolframAlpha, however, the steps it takes to get to that solution aren't clear to me. $x \mod 7 = 3 $ $x \mod 9 = 1 $ $x \mod 4 = 0 $ I also looked into other questions into…
ndaniel
  • 71
0
votes
2 answers

Show that 9453(6824)$\equiv$6782(5675341)$\equiv$2 (mod 5)

Show that 9453(6824)$\equiv$6782(5675341)$\equiv$2 (mod 5) I am very new to modular arithmetic and I am not entirely sure what this question is asking me to do, or how you would go about showing what it is looking for. I apologise if this is very…
Jamminermit
  • 1,923