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

Solutions of $\prod_{i=1}^n x_i = c$ mod p

The problem is: Given constants $c$ and $n$, how many solutions are there to $\prod_{i = 1}^n x_i = c$ mod p? This is the sort of thing that seems like it should be easy but I really have no idea how to do it. Can you give me a hint or two? Thank…
badatmath
  • 4,065
3
votes
2 answers

Can this equation with Modulo be simplified?

I am unsure about how to simplify equations containing the modulo operator (%). Can this expresssion be simplified? (((X - aw) % w) - w) % w The values cannot be assumed to be integers.
Groky
  • 201
3
votes
1 answer

General Exponential modular equation

Can anyone tell me how to solve this equation for lowest $x$ $$a^x \equiv n \mod m$$ other than trying every possible $x$ from $0$ to $m-1$ ($m$ is prime)?
Amit
  • 31
3
votes
2 answers

Eleven test on integers

For this exercise, I need to calculate all possible numbers that satisfy the eleven test. The eleven test is a generalisation of the following: Let $a_1, a_2, a_3$ be numbers. Then it should hold that $a_1 + 2a_2 + 3a_3 (\text{mod } 11)=0$ I tried…
3
votes
1 answer

How to define mod without using integer division or rounding

My brother asked me what the definition of mod was, and I gave him the usual spiel about it being the "remainder" of division. However, he wanted a definition of mod based on functions he understood. He's told me that he has an inherent sense of…
Pro Q
  • 915
3
votes
2 answers

What are the last two digits of $139^{139^{100}}$?

I know that I have to utilize (mod 100) for the problem. Getting use of Euler's theorem as $(139, 100) = 1$ yields $$139^{{139}^{100}} \equiv 139^{{139}^{100} \pmod{\Phi(100)}} \pmod{100}$$ $$ \equiv 139^{{139}^{100} \pmod{40}} \pmod{100}.$$ How to…
3
votes
2 answers

How do I inverse a bijective modulo function?

In my discrete maths homework, I'm being asked to find the inverse of a cipher function: $$f(p) = (3p + 5) \bmod{26}$$ $f(p)$ accepts natural integers of the range ${0,1,...,25}$ (where A = $0$ and Z = $25$) and outputs in the same range. Messing…
zneak
  • 721
3
votes
2 answers

How can I answer this question? (Modular)

$-3 \equiv 17$ Find the mod number. Ex: $-3 \equiv 17 ~~{\rm(mod~5)}$ How would I find the mod number?
suffix
  • 175
3
votes
8 answers

What is the remainder when $4^{96}$ is divided by 6

What is the remainder when $4^{96}$ is divided by 6 My approach : When 4 is divided by 6 gives 4 remainder, when $4^2$ is divided by 6 gives remainder 4 ,... is it for the complete series.. that means when $4^{96}$ is divided by 6 gives 4 as…
Sachin
  • 9,896
  • 16
  • 91
  • 182
3
votes
3 answers

Find all solutions of congruence $3x^2−2x+9≡0\pmod {35}$

Find all solutions of congruence $3x^2 - 2x + 9 ≡ 0 \bmod 35$: Attempt: \begin{align} 3x^2 - 2x + 9 &\equiv 0 \bmod 35\tag{* 3} \\ 9x^2-6x+27 &\equiv 0 \bmod 35 \tag{- 26} \\ (3x-1)^2 &\equiv -26 \bmod 35 \\ \\ -26 + 35 &= 9 = 3^2 \\ \\ \iff…
Vek
  • 303
3
votes
2 answers

Can you use modulus to make 0 > 2?

I wanted to create a rock-paper-scissors game that didn't use a lot of conditionals, and I was wondering if there were any mathematical way of representing the cycle of rock-paper-scissors. So Rock beats Paper beats Scissors beats Rock, or Rock >…
Lou
  • 257
3
votes
1 answer

Find an integer $r$ with $0 ≤ r ≤ 10$ such that $7^{137 }≡ r (\text{mod} 11)$.

Find an integer r with 0 ≤ r ≤ 10 such that $7^{137}$ ≡ r (mod 11). So far I have: $7^{2}$ ≡ 5(mod 11). $7^{4}$ ≡ $5^2$ ≡ 3(mod 11). $7^{5}$ ≡ $3*7$ ≡ -1(mod 11). $7^{135}$ ≡ $(-1)^{27}$ ≡ -1(mod 11). so $7^{137}=(-1)*(5)≡ -5(mod 11)$. I feel like I…
3
votes
1 answer

Why is $(1+80)^t\equiv 1+80t \pmod{25}$ correct?

In a calculation process, I saw a modulo equation $$(1+80)^t\equiv 1+80t \pmod{25}.$$ I can't understand why it's correct. Also, does the modulo equation $(1+n)^t\equiv 1+n^t\pmod k$ always hold? ($n, t, k$ are positive integers.) Any help is…
Iris
  • 411
3
votes
4 answers

Modular Algebra with Powers?

Is it possible to calculate by modular algebra rules (with no calculators) numbers with powers $\textrm{mod}\ n$? Something like: $7^{127} \textrm{mod}\ 11$. If so, how it can be done? Any explanation will be apriciated!
Elior
  • 173
3
votes
3 answers

Solve the congruence $59x\equiv 3\pmod {78}$

The question is: Solve the congruence $59x\equiv 3\pmod {78}$ So I already found the inverse of $59\pmod{78}$ which is $41$. So $41 \cdot 59\equiv 1\pmod {78}$ The solution is: $59x\equiv 3\pmod {78}$ multiplied by inverse is $41 \cdot 59x\equiv 41…
user60334
  • 717