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

how to use modulo in this formula

I Have this formula: $$(n-1)!(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4})$$ $2\le n\le 100000$. I would like to modulate the result of this from this formula by any modulus, but for the moment let's assume that it is constant, MOD = 999999997.…
0
votes
2 answers

Is there $a\in \mathbb{Z}$ such that $ a^2\equiv 2 \pmod3$

Is there $a\in \mathbb{Z}$ such that $$ a^2\equiv 2\pmod3$$ I did the following : if the equation is true then one has $(a-1)(a+1)\equiv1 \pmod3$ which implies that necessarly that both $(a-1)$ and $(a+1)$ are not even hence $a$ is an even number…
BrianTag
  • 1,395
  • 7
  • 18
0
votes
0 answers

When a mapping $r \rightarrow r^x\;\text{mod } n$ is a permutation of $\{1,\dotsc,n\}$

I was studying Blind RSA signature scheme (wiki) where we have a standard RSA setup: $p, q$ are some prime numbers $n = pq$ $ed = 1\; \text{mod }\varPhi(n) $ On top of that, there is some random number $r \in Z_n$ In the Wikipedia page it says…
kopi22
  • 11
0
votes
0 answers

What are the modular arithmetic properties when taking the modulo of an expression with an irrational fraction?

Under the identities section in this Wikipedia page they list the distributive property for multiplication. However it doesn't hold true for fractions. Is there a list of modulo properties when fractions (particularly irrational fractions) are…
0
votes
1 answer

What mistake did i do here? Inverse modulo calculation

I want to find the inverse of $56 \bmod 5$ so $56x \equiv 1 \bmod 5$. With the eye we can easily see that $x=1$ but i want to follow the procedure. So i proceed with the extended Euclidian algorithm $56 = 11 \cdot 5 + 1$ So $1 = -11 \cdot 5 + 1…
Than1
  • 331
0
votes
2 answers

Struggling to understand the last step of finding the inverse modulo procedure

I want to find the inverse of $7 \bmod 18$. First of all i found that $gcd(7,18)=1$ Then i express the $gcd$ as a linear combination of $7$ and $18$ using Euclidian algorithm $1=(-5)7+2(18)$ All good until now. However after that the textbook does…
Than1
  • 331
0
votes
1 answer

Solving $2444 = 960x \pmod{2618}$

I am trying to teach myself modular arithmetic to solve a programming challenge. Basically it needs to solve this kind of system of modular equation, \begin{align*} 2444 = 960x \pmod{2618} \end{align*} except the number is very large. I know the…
0
votes
1 answer

RSA simple exercise

An exercise asks me to encrypt with RSA a message m=10. The public key e=11 and the private key d=11. The modulo is 60. So i tried first to cipher this way: C=10^11 mod 60=40 So 40 is my ciphertext. Then the exercise asks me to decrypt it. So I did…
Jhon
  • 11
0
votes
1 answer

Find $b$ if $5^b\equiv 2345[2^{12}]$ is given.

Given $5^b\equiv 2345[2^{12}]$ for some positive integer $b$. Also, given order of $2345$ modulo $2^{12}$ is $2^9$ and order of $5$ modulo $2^{12}$ is $2^{10}$. We are to find $b$. What I tried is the following. We know if $a$ be a group element of…
KON3
  • 4,111
0
votes
1 answer

What does A ≡ B mean exactly without the modulo?

If A≡B(mod C) then is there any logic in saying something like A≡B? Does A≡B mean anything without the context? Here's an example problem my math professor solved during class. In part a, he takes (5^100)^2 ≡ 13^2. To me this is implying that 5^100…
BobaJFET
  • 113
0
votes
0 answers

What rule was used and we changed the sign in this inv multiplicative mod?

I don't understand the exact steps the following statement is using in regards to what is the multiplicative inverse of $13 \mod 40$ One can find a multiplicative inverse of $13$ by observing that: $13 \cdot 3 = 39 \equiv -1 \mod 40$ (a) Hence $13…
Jim
  • 1,589
0
votes
1 answer

Finding all solutions for congurence when m equals $2$

I am reading the following exercise: Find all solutions to the congruence $3x \equiv 5 \mod m $ when $m$ equals $2$ The solution states: Since $3 \equiv 5 \equiv 1 \mod 2$ the congruence is equivalent to $x \equiv 1 \mod 2$. There is one solution…
Jim
  • 1,589
0
votes
0 answers

Simultaneous modular equations

I'm reading Cox's "Primes of the form $x^2+ny^2$", and Lemma $2.5$ reads: "...Conversely, suppose $D=b^2$ mod $m$. Since $m$ is odd, we can assume that $D$ and $b$ have the same parity (replace $b$ by $b+m$ if necessary) and then $D=0,1$ mod $4$…
JBuck
  • 681
0
votes
1 answer

Number Theory Modulo

I need to prove that if $k\cdot a \equiv k\cdot b \ \ (mod \ n)$ then $a \equiv b\left( \mod \ \frac{n}{gcd(k,n)} \right)$ I tried to do this: $$ k(a-b)=s\cdot n \\ k=u\cdot \gcd(k,n) \wedge n=v\cdot \gcd(k,n) \ ; \gcd(u,v)=1 \\ u\cdot \gcd(k,n)…
JollyQ1
  • 63