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

Compute $\phi(24)$. For each element $\mathbb Z /24$ decide whether the element is a unit or a zero divisor.

Possible Duplicate: Euler $\Phi$ Function $$\underline{Question}$$ Compute $\phi(24)$. For each element $\mathbb Z /24$ decide whether the element is a unit or a zero divisor. If the element is a unit, give its order and find its inverse.…
0
votes
2 answers

$x_{11} = x_1 + x_2 + x_3 + \cdots + x_{10} \pmod{9}$ Help determining the check digit

I need help determining what operation I would use to determine the check digit of this equation \begin{eqnarray*} x_{11} = x_1 + x_2 + x_3 + \cdots + x_{10} \pmod{9} \end{eqnarray*} Those are sub numbers, rather than $x \times 11$. I don't know…
0
votes
1 answer

Determining solutions to congruence equations

The first exercise states: Suppose that $a$ and $b$ are integers, such that $a \equiv 12 \pmod{5}$ and $b \equiv 3 \pmod{5}$. Given $c \equiv a \cdot b \pmod{5}$, find $c$ in $\mathbb{Z}_5$. The second exercise states: Suppose that $a$ and $b$ are…
0
votes
1 answer

multiplicative inverses in modular arithmetic - breaking up a modulus

Let $p_1$ and $p_2$ be distinct primes. Is it always true that the solution of the simultaneous congruence $$ax \equiv 1 \mod{p_1}$$ $$ax \equiv 1 \mod{p_2}$$ is a solution to $ax \equiv 1 \mod{p_1p_2}?$
Adam
  • 3,422
  • 1
  • 33
  • 50
0
votes
2 answers

How to prove the uniqueness of multiplicative inverse modulo n?

From here, I have learned However, I can't figure out why can it replace $1$ with $xc$, there is no such property here
Chen Li
  • 117
0
votes
3 answers

How to find remainder of denominator is greater than numerator?

I am learning modular arithmetic and trying to figure out, how to find remainder where denominator is greater than numerator? For example: i) $2 \bmod 5 =$ ? I tried to solve this but I got 0 as remainder whereas in calculators it is $2$ . I was…
Alena
  • 103
0
votes
1 answer

Solve $a \equiv b^c \pmod {d}$ for $c$

I'm trying to solve the following equation for $c$. $$a \equiv b^c \pmod {d}$$ I'm given arbitrarily large numbers ($a$, $b$, and $d$ to solve for c, examples below), but it's just not feasible to iterate through every possible $c$ and check (using…
0
votes
2 answers

Resolve an equation that uses remainders

I wan to know how to solve this equation where $\rm\ D $ and $\rm\ k $ values are know and I want to find $x$: $x (x\ mod\ k\ ) ^ 2 \rm\ mod\ k = D$ And I dont know how to start and how to exactly the problem is expressed in math notation. I…
0
votes
2 answers

$a * x \equiv a \pmod n$ other than $x = 1$

This is probably a very basic question, but beeing new to modular arithmetic it's difficult to to search for an answer without knowing a name for the concept. So for given $a$ and $n$: $$a * x \equiv a \pmod n$$ Is there a name for such $x$? Is…
Niklas
  • 488
0
votes
5 answers

Calculate the remainder of $2^{118}/5$

I have a problem: $2^{118}/5$, calculate the remainder I think I should use modular arithmetic but I cannot understand it. I assume I should apply $a^t\equiv b^t\mod n $ I have so far written: $2^{118} \mod 5$ And I know that I should convert the…
0
votes
1 answer

Given $a\le1025$ , Find Minimal non-negative $y$ such that $1025 \equiv 0\mod (a+y)$

General solution that works with not only $1025$ but also any given number is preferable.
elise
  • 9
0
votes
2 answers

How is it that value1 * a + b mod x= value2 * a + b mod x without value1 and value2 being equal?

How come for any primes $x$ and positive integers $a,b \in \mathbb Z$ that $$( \text{value 1} \cdot a + b) \ \text{mod} \ x = ( \text{value 2} \cdot a + b) \ \text{mod} \ x$$ even when $\text{value 1} \neq \text{value 2}$? I can't find a correlation…
Mine
  • 127
0
votes
0 answers

Is there such a concept as "modular sets" and their properties?

I have a question. Using the Chinese Remainder Theorem, it's easy to find the (lowest) solution to a series of modulus statements. For instance, given: x mod 5 = 3. x mod 7 = 2. x mod 11 = 9. the solution (163) is fairly straightforward to find.…
0
votes
1 answer

determine if a looped sequence $A=(a_0\ldots a_n)$ can be represented as $A_i=(p^ia+b\sum_{k=0}^{i-1}{p^k})\pmod M$

Suppose there's a looped sequence $A=(a_0\ldots a_n)$ and, since it is a looped sequence, $a_0=a_n$. Given $M$, is there a way to determine whether said sequence can be produced by a formula $$A_i=(p^ia+b\sum_{k=0}^{i-1}{p^k})\pmod M$$ In other…
Thehx
  • 183
0
votes
4 answers

Why must all common factors of x and y also be factors of gcd(x,y)?

I have found a pretty convoluted proof for this phenomenon, but I cannot figure out an intuitive explanation, so that is what I am looking for.