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

What is a multiplicative inverse?

From my understanding, the “multiplicative inverse” of a number is what you have to multiply it by to get $1$, i.e. the inverse; in general, the multiplicative inverse of $x$ would be $\frac{1}{x}$. However, I came across a question to do with…
mimyo
  • 198
  • 10
2
votes
1 answer

Fast modulo operation

Possible Duplicate: calculating $a^b \!\mod c$ I have a number of form: $p^n + p$, where $p$ is a prime number and $n$ can be any large number, for example, say $10^{12}$. What is the generic algorithm to compute $(p^n + p) \pmod k$, where $k$…
JCH
  • 197
2
votes
0 answers

What is the remainder when $a$ is divided by 6?

An integer $a$ leaves the same remainder when divided by $3$ and $12$, it also leaves a remainder of $2$ when divided by $4$, what is the remainder when $a$ is divided by 6? Here's my attempt, would be glad if someone can confirm whether if I'm…
2
votes
1 answer

Exponential modular equation

I am having some trouble in proving that the only solutions to $$ -2^{m-1} \equiv m \pmod{7} $$ are $m \equiv 3,5, 13 \pmod{42}$. What I tried to use: If $-2^{m-1} \equiv m \pmod{7}$, then $2^{m-1} \equiv 6m \pmod{7}$ and we know that $2^6 \equiv 1…
JPLF
  • 590
2
votes
1 answer

Double constraint in modular arithmetic

Find all integers $x$ such that $x ≡ 5 (\mod 8)$ and $x ≡ 73 (\mod 81)$. Should I think like this: $x = 5 + 8a$ $5 +8a = 73 + 81a → 68 = 72a$ After that I'm stuck.
2
votes
1 answer

Given two integers for which I know the modulo given a divisor, what can I know of the modulo of their multiplication?

With all symbols representing integers, I know: $$ a \equiv m_a \bmod d_a \\ b \equiv m_b \bmod d_b $$ And I am now looking for $m_c$ and $d_c$ such that: $$ c = ab \\ c \equiv m_c \bmod d_c \\ \forall d_c', m_c': c \equiv m_c' \bmod d_c'…
Oak
  • 193
  • 6
2
votes
4 answers

How to solve $9^{-1} \bmod 11$ mentally

I want to know whether there is a mental way to solve modulus equations viz. $9^{-1} \bmod 11$ or any equation where the inverse is less than the mod. I can solve $11^{-1} \bmod 9$, but the reverse way confuses me.
2
votes
2 answers

Is there a faster way to calculate $3^{12000027} \pmod{35}$ than the right-to-left binary method?

I've been asked to calculate $3^{12000027}\pmod{35}$ without the use of a calculator. I'm new to modular arithmetic, so I searched for the possible approaches to this problem. The fastest way I could find is the right-to-left binary method described…
Overv
  • 177
  • 1
  • 6
2
votes
1 answer

Problem with Modulus and division

Suppose I want to compute $(a_1 + a_2 + ... + a_n) \mod m $. For very large values of $a_i$, I can take modulo after every operation: $ [(a_1 \mod m) + (a_2 \mod m) + ... + a_n \mod m] \mod m$ (I don't want the values to exceed their data-type's…
2
votes
1 answer

Maximize a linear equation with a modulo

How can i maximize the function of the type (ax + b) % c where a, b, c are constants and are given while x is a integer variable ? I'm not getting any idea how to start solving such problems.
2
votes
2 answers

Mod with a negative number

I know how $\div$ and $\mathrm{mod}$ works but I have come across the following example and I do not understand it: $-117 \pmod {352} = 235$ Shouldn't that be equal to $-117$?
kelua
  • 23
2
votes
2 answers

prove $a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\times p_2}$

I am following a proof of an RSA algorithm and the proof states the following: $p_1$ and $p_2$ are distinct primes, $a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\times p_2}$. Let's call that FACT X. can someone…
2
votes
1 answer

basic modulus question

So if so $a \equiv b \pmod{n}$, which should be read as "$a$ is congruent to $b$ modulo $n$" which from what I understand is something among the lines of "$a$ is the remainder when $b$ is divided by $n$". Now, given $51 \equiv 41 \pmod{5}$ means the…
2
votes
2 answers

Application of Fermat's Little Theorem/Fermat Euler Theorem

Find an integer $x$ with $0\leq x \leq73$ such that $$2^{75}\equiv x \pmod{74}$$ I think I'm supposed to be using either Fermat's Little Theorem or the Fermat-Euler theorem here but I don't think I can do it directly because $74$ is not prime nor do…
MHW
  • 2,940
2
votes
2 answers

$12^7+8^8$ divided by $13$

I Need to find what the remainder is when $12^7+8^8$ is divided by $13$ I have a solution, but don't know if it is right. $12=-1\mod13$ $12^7=-1\mod13$ $8=8\mod13$ $8^2=6\mod13$ $8^4=10\mod13$ $8^8=9\mod13$ Then I did $-1\mod13+9\mod13=8\mod13$, so…
Hannah
  • 21