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

Cyclic Allocation, Defining the Worker's Set

Cyclic allocation is a method of assigning $n$ tasks to $p$ workers. The foreman allocates task $k$ to worker $k \mod p$. $$a = k \mod p$$ Now I am interested in how the worker can calculate his allocation without the help of the foreman. As he…
jsj
  • 535
0
votes
2 answers

Finding $x$ that makes $x^2 ≡ 1 (\mathrm{mod} \ n)$, when $n$ is a composite number

How do I find $x$, $( x > 1)$, that makes $x^2≡1 (\mathrm{mod} \ n)$, for any natural number $n$?
0
votes
4 answers

Solve for x: $bx \equiv a \pmod p$

I am trying to solve $bx \equiv a \pmod p$ Where a,b,p is known and p is a prime. For example: $14x \equiv 1 \pmod p \implies x = 4$ Is there an efficient algorithm to solve this equivalance? I feel a bit daft for asking this as I think I should…
0
votes
2 answers

Modular arithmetic of numbers

let us consider two integers a,b that are co prime to a prime number p Then is there any relation between a%p, b%p and ab%p ? % = modulo operator
hanugm
  • 2,353
  • 1
  • 13
  • 34
0
votes
1 answer

Find $n$ that satisfies $t\equiv nr\pmod{q}$, if such $n$ exists.

So basicially, given the equation $t\equiv nr\pmod{q}$ where $t,r\in\mathbb{N_0}$ and $n, q\in\mathbb{N}$ find $n$ if the rest of the variables are defined. I've figured out a way to see if there is a solution. It appears that if the largest common…
Luka Horvat
  • 2,618
0
votes
1 answer

Modular equation inverse of itself

What is $a^{-1}\pmod a$? From what I've tried it came out to be zero because $a^{-1} = a * a^{-2}$ $a^{-1} \pmod a = a * a^{-2} \pmod a$ $a * a^{-2}$ is divided by $a$ so the result should be zero. Is my proof right?
More Code
  • 221
0
votes
1 answer

Modular Rules& Arthimetic

If $x=3 \mod 11$ and $x=3 \mod 19$ is there a modular formula/rule that can combine both statements together? If $x=5 \mod 9$ is there a modular formula/rule that can convert $x=5 \mod 9$ into $x=r \mod 11$, where r is some arbitrary integer?
jessica
  • 1,002
0
votes
2 answers

Show that $\{1, 4, 7, 13\}$ is closed under multiplication $\bmod 15$.

How do I show that $\{1,4,7,13\}$ is closed under multiplication $\mod {15}$? I know it's closed. Is there a rigorous way to show it?
0
votes
1 answer

Modular Arithmetic calculation

(a) $x+40 ≡ 1 \pmod {99}$. (b) $40x ≡ 1 \pmod {99}$. Is the answer for a $x \equiv -39 \pmod {99}$ and b $x\equiv\frac{1}{40}\pmod {99}$? I believe I am doing it correctly.
modlim
  • 1
0
votes
1 answer

Solving modular arithmetic questions

I am having trouble finding mod arithmetic questions. Can you show how to solve these? $x + 30 \equiv 1 \pmod {12}$ $30x \equiv 1 \pmod {12}$ $x + 3y \equiv 1 \pmod {12}$ and $2x + y \equiv 7 \pmod {12}$
modlim
  • 1
0
votes
1 answer

Modular Arithmetic Question mod

I am having problems solving two-variable mod equations. How would one solve this? $$ \left\{\begin{aligned} x + 3y &\equiv 1 \pmod{11} \\ 2x + y &\equiv 7 \pmod{11} \end{aligned}\right. $$
modlim
  • 1
0
votes
1 answer

Set builder modular arithmetic

I have a set C which is defined as: $$ C= \{ (x|x\in \mathbb Z^+) \land ( x \pmod 3 < 2) \} $$ To find such an x, we have: $x = 3n + 1$ But what am I limited to in this case? if $ n=1 $ then $x=4$. But am I limited to positive integers less…
Dimitri
  • 1,287
0
votes
0 answers

Modular arithmetic confusion

I am a bit confused about modular arithmetic. We say that two integers are equal modulo n if their difference is an integer multiple of n. So let's take as example: $5(mod2) = 1$, since $5-1 = 4$ which is an integer ($k$) multiple of 2. But isn't…
Stallmp
  • 406
0
votes
0 answers

Let $a,m,s,t$ be integers, with $m > 0$ and gcd$(a,m)=1$. Show that if $a^s \equiv a^t \pmod{m}$, then $s \equiv t \pmod{\text{ord}_m(a)}$.

I have been able to show this for a specific example, but I am at a loss of how to formally prove it. I know, by Euler's Theorem, that $a^{\phi(m)}\equiv 1\pmod{m}$, but I am unsure of what to do with it. I don't need anyone to write the proof for…
0
votes
0 answers

Inverse Modulo for use in Cryptography

I am investigating the hill cipher. The determinant of my encryption matrix is a negative number, and I need to find the inverse modulo (using mod 26) of this determinant. This is eventually used to create the deciphering matrix. Do I take the…