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
1
vote
0 answers

Why does this imply these two numbers are the same mod 8?

I was looking over the solution to a problem here (http://www.artofproblemsolving.com/Wiki/index.php/2013_AMC_12B_Problems/Problem_14). What has me confused, is where they say that $5x_{1} + 8x_2 = 5y_1 + 8y_2, x_1 \neq y_1, x_2 \neq y_2$ implies…
Anony
  • 11
1
vote
1 answer

Find $e \in \{0,1,\ldots,22\}$ such that the product $\prod_{i=6}^{18} i$ is congruent to $e$ modulo $23$

Find $e \in \{0,1,\ldots,22\}$ such that the product $\prod_{i=6}^{18} i$ is congruent to $e$ modulo $23$. I have completed a question similar to this before so I thought I knew how to do this but I believe my answer is wrong. In order to complete…
1
vote
0 answers

How do I Multiply Out Modular Division?

How do I multiply out modular division(s) to simplify for x? I am trying to tackle a coding problem and I'm hopeful that I can simplify the equation in terms of $x$ ($x = ???$) from the following statement: $$b\mod{x} = x \mod{a}$$ Example: $x=6$…
1
vote
0 answers

Solving congruences with addition

Can anyone help me to understand what to do with the subtraction or addition on the LHS of a congruence? I found this question - Solving congruences involving addition for CRT But I don't understand how the answer goes from $$7j+6\equiv 4 \pmod{5}$$…
null
  • 111
  • 2
1
vote
1 answer

Can you explain the thought process behind this this modulo operation

We want to find the minimum natural number that satisfies the equation $2^{100} \equiv x \bmod 9$ Textbook says: We observe that $2^{3} \equiv 8 \equiv -1\bmod 9$ After that it simply breaks down $2^{100} $ until it reaches the desired…
Than1
  • 331
1
vote
2 answers

Modular arithmetic with coprime numbers

Let $m$ and $n$ be coprime. By doing a few concrete examples, I see that the numbers $0,m,2m,3m,\dots,(n-1)m$ get mapped to the numbers $0,1,2,\dots,(n-1)$ in $\operatorname{mod}(n)$. How do I show that when going from $0$ to $(n-1)m…
matt
  • 876
1
vote
1 answer

Non-trivial solutions to modular arithmetic of composite numbers

I have been looking at $x^2 - x \equiv 0 \pmod 6$. Factoring $x^2 - x$ yields: $$x^2-x = x(x-1)$$ Solving $x(x-1) \equiv 0 \pmod 6$ implies $x \equiv 0$ or $x \equiv 1 \pmod 6$. However, these are not all the solutions. As it turns out, $x \equiv…
Josh
  • 1,086
  • 4
  • 15
1
vote
4 answers

Modular arithmetic: How to solve $3^{n+1} \equiv 1 \pmod{11}$?

Please, I can't solve this equation: $$3^{n+1}\equiv 1 \pmod{11}$$ for $n \in \mathbb{N}$. So what should I do please? Thanks.
1
vote
4 answers

Find the remainder in the division of $3^{385}$ by $400$.

Find the remainder in the division of $3^{385}$ by $400$. What I thought: I'm looking for the smallest $r$ such that $3^{385} \equiv r \pmod {400}$. Which is equivalent to the system $\begin{cases} 3^{385} \equiv r \pmod {2^4} \\ 3^{385} \equiv r…
BrKo14
  • 105
1
vote
0 answers

Congruence proposition proof

I was given this question, suppose that $x\equiv y(\mod mn)$, show that $x\equiv y(\mod m)$ and $x\equiv y(\mod n)$, is this proof correct, do we need to have $\gcd(m,n)=1$? We have $x\equiv y \mod m\times n\Rightarrow mn|(x-y)\Rightarrow \exists…
aliberro
  • 408
1
vote
1 answer

Egg dropping problem utilising binomial coefficient and Luca's Theorem

Currently I'm solving an interesting performance variant of the egg dropping problem from codewars for which I need your help. The following equation is given: \begin{equation} f(d,n) = \sum_{i=1}^{n}{d \choose i} \end{equation} d represent the…
Jan L
  • 43
1
vote
1 answer

Better way of finding multiplicative inverse?

This summer I am taking a cryptology class and a common task we need to do is finding the modular inverse. When finding the modular inverse for the following I would do it like so: 12 mod 23 23 mod 101 I just start at 1 and count by the modulo…
1
vote
0 answers

Congruence a is congruent to bmod(n) is the same as amod(n) = bmod(n)

Good afternoon. I am relatively new to modular arithmetic. I have been asked to show that if $ a\equiv b,\ b\equiv c \pmod n$, then $a\equiv c \pmod n$. My idea was to write that $a\equiv b \pmod n$ is the same as writing $a \bmod n = b\bmod n$.…
1
vote
2 answers

Completing the square modulo $p$

(Admittedly, this question is inspired by one of the questions I was thinking for my Algebraic Number Theory class but I don't think the question that I am about to ask needs much knowledge of Algebraic Number Theory.) Suppose $d$ is an integer that…
1
vote
2 answers

Is there some nomenclature to get the remainder of a value?

I want to write a formula where I can say that I have to get the remainder of a division by 4. $y = \mathbf{remainder}(x\div4)$ Is there any math nomenclature I can use?
Fabricio
  • 421