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

Find the smallest value of $n$ such that $3n^3-2019$ is a multiple of 2016

I've been struggling with this question for a while. So far I've gotten up to n^3 ≡ 1 mod 672 and I am not sure what I can do from here. Thank you!
0
votes
1 answer

How to calculate $3^{-1}$ modulo $2$ and modulo $3$?

I have to figure out these, but i dont know how: $3^{-1}\equiv x \pmod{2}$ $3^{-1} \equiv y \pmod{3}$ For modulo $2$ my idea is that: $1 \equiv 3 \pmod{2}$ divided by 3: $3^{-1} \equiv 1 \pmod{2}$ But what about mod $3$?
user600857
0
votes
2 answers

11x - 7 = 0 (mod 13), What is this?

11x - 7 = 0 (mod 13), What is this? The answer is 11x/13 = 13n + 3, for n = 0,1,2,3 But what is that (mod 13) means. Does this mean that you are taking the mod on both side of the equation or what?
kou
  • 159
0
votes
3 answers

Show $a^k ≡ b^k\pmod m$

I need to show that if $a,b,k$ and $m$ are integers and $k ≥ 1, m ≥ 2$, and $a ≡ b\pmod m$, then: $a^k ≡ b^k \pmod m$. But I have no idea how to show this, I have never been this confused. So is there anyone who could help? just a little, like I…
0
votes
0 answers

a question from modular arithmetic

Given $a,b$ in $Z_N$* for some composite positive integer N. Let the bit sizes are $a_N , b_N , N_N$ respectively. Also $a_N = (N_N$ or $N_N-1) , a
smslce
  • 163
0
votes
2 answers

How to Find an exponent of a power in a congruence

I need to solve: $2^k\equiv7(\text{mod }30)$. Also there exists a homomorphism $\varphi: U_{30}\rightarrow U_{30}$ such that $\text{Ker}(\varphi)={\{\bar{1},\bar{11}\}} $ our teacher chalenged us also to solve: $x^k\equiv7(\text{mod }30)$, i.e.:…
eagleye
  • 113
0
votes
3 answers

Find integers $b, c $ so that $3b\equiv3c\pmod{12}$, but $b \not\equiv c\pmod{12}$.

$$3b\equiv{3c}\quad(\text{mod }12),$$ but $$b\not\equiv{c}\quad(\text{mod }12).$$ I am not sure how to approach this problem, any help is appreciated. Thanks!
gofish
  • 369
0
votes
5 answers

How to show steps for 11x - 7 $\equiv$ 0 (mod 13)?

I know the answer is $x = 3$, but I'm having trouble showing the steps for it. All I have is $11x \equiv 7 (\mod 13)$.
gofish
  • 369
0
votes
1 answer

Is 1 always a modular inverse of 1?

I have been looking for an answer online but I am unable to find one. Are inverses defined as to not include the number 1? Would this mean that 1 is an inverse of itself in $1*1^{-1}=1 (\textrm{mod p})$ where p is any number?
S5amuel
  • 11
0
votes
1 answer

Solving an equation with residue classes?

I want to show that in ℤ6, the equation [2]X = [0] has a solution, but the equation [2]X = [5] does not. However, I am unsure how to find the solution to X, specifically, how to divide residue classes? I know that how addition and multiplication…
0
votes
2 answers

Find all numbers between 1900 < b < 2000 that are congruent to a mod m...

So when $a = 1$ and $m = 13$ I know that by the definition of congruence, $$13 \vert (1 - b)$$ which means $$b = 13k + 1, k \in \mathbb{Z}$$ And then $$1899 < 13k < 1999$$ I'm not sure how to proceed from here.
Stuy
  • 1,149
0
votes
1 answer

Modular exponentiation with operations in the exponent

I’m trying to know how to calculate step by step the next equation applying the module in each operation: $2^\left(4 \times \frac{6}{8}\right) \pmod{11}$ I know that if I just solve the whole equation and then I apply mod 11, the result is 8. $4…
Jolo
  • 13
0
votes
0 answers

Math Equation Using % / Modulus / Remainder

So in javascript programming you get a % / Modulus / Remainder operator. It divides a number by the max amount it can be divided by (dropping decimals), and then returns what is left after this max division. Here are some practical examples: 6 % 3 =…
0
votes
1 answer

Multiply number by its own modular inverse and a constant

We are given the following constant: e = 17 We generate a random 64 bit prime p and then calculate q so that: q = modinv(e,p) This process is repeated until q is prime as well. Now I ran this and generate the following pair: p =…
S. L.
  • 157
0
votes
1 answer

Using modular arithmetic

When the number $357a$ is divided by $5$, the remainder is $2$ Evaluate the values $a$ can take. I'm aware of the fact that we could just take a look into divisibility rule of $5$, which yields $a \in \{0,5\}$. Since the remainder is $2$, we…
Busi
  • 572