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

Multiplicative Inverse of Modulo n is UNIQUE

I am trying to prove this: $x,b,n\in \mathbb{Z}, \space xb\;(\mod{n}\;) = 1 \implies $ b is unique. I have tried by using proof by contradiction. That is, assume there are integers $b,c$ where the above first condition is satisfied. Then we know…
3
votes
6 answers

$\frac{7}{5} \equiv 11 \pmod{12}$. Why is it $11$?

I know this equation is true but I don't get the reason $\frac{7}{5}$ is congruent to $11$ here. The quotient is supposed to be $1.4$ in non modular arithmetic and I don't get where $11$ has come from.
Lullaby
  • 31
3
votes
1 answer

Rules for modulo of bitwise xor

There are rules for modulo operation involving summation, multiplication and division. For example: (A + B) % P = (A % P + B % P) % P (A * B) % P = (A % P * B % P) % P (A / B) % P = ((A % P) * (B^(-1) % P)) % P where % means modulo operation and…
3
votes
5 answers

How to find $2^{37} \bmod 77$?

Is there any quick way to find $2^{37} \bmod 77$? I have tried breaking it down into 2 components for example .. $2^{37} \bmod 7$ and $2^{37} \bmod 11$ but still no luck. Any ideas? Thanks
3
votes
1 answer

Diffie Hellman calculate number

I want to solve this Diffie Hellman problem: public number: $g=5$ prime number: $p=23$ Alice: Secret number $a < p$, $m\equiv g^a\mod p$ $m=21$ Bob: Secret number $b < p$, $n=g^b\mod p$ $n=6$ Now I am searching for $a$ and $b$. How can I do…
kilDasd
  • 31
3
votes
3 answers

Find inverse of $[-2] \bmod 5$

Given the equation: $$42x\equiv 1\pmod 5$$ I have determined the class $[-2]_{5}$ as $x$ solution of the given equation. Now I have to find the inverse of $x$ (i.e. $x^{-1}=[-2]_5^{-1}$ ). As far as I know, the $x=[-2]_5$ first found is just…
BAD_SEED
  • 463
3
votes
0 answers

Simplify this number using modular arithmetic.

Find the last 10 digits of the number $9511627776^{195761}2^{17}$. Well, I know I just have to perform $$9511627776^{195761}2^{17} \mod 10^{10}$$ and I know that $195761$ is prime. Also, $9511627776 \equiv 2^{40} \mod 10^{10}$. Where do we go from…
Don Larynx
  • 4,703
3
votes
1 answer

Inverses modulo a prime power

My question relates to inverses modulo $p^k$ for prime $p$. I came across an article that gave a recurrence relation for computing inverses modulo $p^{2^n}$, but it did not make clear how (or even if) they might be combined to produce the inverse…
Jim White
  • 616
3
votes
1 answer

Modular exponentiation twice over

What is a general way to calculate something like $2147089412^{1147068432^{647017654}}\pmod m$? It looks like modular exponentiation, but how do you reduce the highest part properly? Note: $m$ is prime Result: Case 1: Where $\text{left}\equiv…
2
votes
1 answer

Solving/simplifying large mod

Sorry for my English, it's not my first language and that's a lot more evident when we talk about math. I'm currently taking a cryptography class in university and we have to deal with very big mod numbers, I'm familiar with using Fermat and Euler…
Joao
  • 21
2
votes
0 answers

Divisibility in different Modulo.

So I've actually been working with congruences recently in class and most of the time I end up using Fermat or the Euler Totient function to simplify a large exponent. In general, I run into a situation where I find : $a^y = z $ (mod n) I know…
user145003
2
votes
1 answer

How would you solve this modular equation without being able to find the multiplicative inverse?

If I have $15a \equiv 60 \space mod \space 95$, how could I solve for $a$? The equation has multiple solutions (23 and 42 among them) -- how do I find them without resorting to guess-and-check?
Tyler
  • 287
2
votes
1 answer

Why is any number to the 1,5,9,13, etc. modulus 10 itself?

Why is $n^{4k+1} \% 10 = n$ for any integer $n$ and any whole number $k$? What about base 10 math makes this so?
2
votes
4 answers

How do you find the modular inverse of $5\pmod{\!11}$

I need to find out the modular inverse of 5(mod 11), I know the answer is 9 and got the following so far and don't understand how to than get the answer. I know how to get the answer for a larger one such as 27(mod 392) but am stuck because they are…
user2956865
  • 33
  • 1
  • 4
2
votes
2 answers

Chinese remainder theorem

I am looking for a simple proof to show that given a countable set of natural numbers $C$ that is closed under addition and whose gcd is 1, there exists two elements $c_1, c_2 \in C$ such that $\gcd(c_1, c_2)=1$. I used the Chinese remainder…
Neil G
  • 2,479