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

Recover $m$ from $k = n \mod m$ when $k$ and $n$ are known

I was wondering if there is a quick way how you could find (calculate, bruteforce) $m$ in $k = n \mod m$ if you know $k$ and $n$.
Wouterr
  • 111
0
votes
0 answers

Help Solving $m(m-1) \equiv 0 \pmod n$

Is there a way to solve the equation $m(m-1) \equiv 0 \pmod n$ for $1 < m < n$? In this case, $n$ is known and I am solving for $m$. I am especially interested in either the highest or lowest value of $m$ given the listed bound, though finding any…
0
votes
1 answer

Is it possible to calculate x having all other information in ((x^3)+5) mod p where p is a known large prime?

Please kindly note that I am a beginner. My questions are these: Is it possible to calculate x from the following data? If yes, how? If not, why not? ((x^3)+5) mod 111267492025176636775873676207109540284671533365944463094334269908178130251703 =…
Robert
  • 117
0
votes
0 answers

How to show that $(a \text{ } mod \text{ } m)^2 \text{ } mod \text{ } m = a^2 \text{ } mod \text{ } m$?

I have seen this small equality used in a proof that I was reading and I wanted to show that it is true. It seems like an easy problem but I didn't know how to start. Can you show me how is it true?
0
votes
3 answers

Congruence $n*2^n + 1 \mod 3$

I want to investigate for which $n\geq0$ the expression $n*2^n + 1$ is divisible by $3$. I’ve tried applying Fermat’s little theorem but without any success and believe this is not the correct way to go about it. Any tips or hints would by highly…
user690277
0
votes
1 answer

How to solve inverse modulo?

Inverse modulo can be solved easily by Euclidean algorithm but 3 to the power minus 13 mod 2 can not be easy, I appreciate if anybody can give a solution. For example: $3^{-13} \bmod 2 = ?$
Biswas
  • 1
0
votes
5 answers

Sum of powers of $3$ modulo $8$

What is $(3^1+3^2+\cdots+3^{2015})\bmod{8}?$ I'm really bad at these kinds of problems so a thorough explanation would be much appreciated.
0
votes
3 answers

Can someone explain the following modular arithmetic?

$7^{-1} \bmod 120 = 103$ I would like to know how $7^{-1} \bmod 120$ results in $103$.
0
votes
2 answers

Property of modular arithmetic.

(a / b) % c = ((a % c) * (b^{-1} % c)) % c How to calculate b^{-1}? I know it is not 1/b. Is there more than one way to calculate this?
0
votes
2 answers

Remainder is less than divisor

I'm reading a book and it says the equation $$ a \bmod n = a - n \left\lfloor\frac{a}{n}\right\rfloor$$ follows that $$ 0 \leq a \bmod n \lt n. $$ I understand that the remainder is less than divisor, but I can't understand how the author got it…
0
votes
1 answer

$\lfloor{\frac{a}{b}}\rfloor\bmod c$

$~a~$ is sum of finite GP series$$1 + x + x^2+ .. +x^n,\qquad n\lt 10^{18}$$ $(0\lt b\lt 10^3)~\text{and}~(0\lt c\lt 10^9)$ I have used, $~a\bmod b = a - b\lfloor{\frac{a}{b}}\rfloor$ $\implies \lfloor{\frac{a}{b}}\rfloor = {\frac{(a - a\bmod…
0
votes
1 answer

How to calculate modulo of a factorial?

I am using C++ programming language. We are given 3 integers $x,y,z$ and I have to calculate :- $(x +y +z)!/(x!*y!*z!) $ modulo $p$ where , $p=10^9+7$ Also , $0<=x,y,z<=10^5$ I tried many approaches but none of them worked. Fermat's theorem also…
0
votes
1 answer

Equation : $x^2+1\equiv 0\mod {p}$. admits only two solutions if $p\equiv 1\pmod{4}$

I need help on how to prove that this equation $x^2+1\equiv 0\mod {p}$ ;where p is a prime number, admits only two solutions if $p\equiv 1\pmod{4}$?
Kamal
  • 648
0
votes
2 answers

What is the remainder of $3^{2020} / 7$

I tried to solve this problem like: Remainder of $3^2 / 7$ is $2$ Remainder of $3^3 / 7$ is $-1$ Then i square that, and I get Remainder of $3^6 / 7$ is $1$ Then I can go all the way to: Remainder of $3^{2016} / 7$ is $1$ Now how do I get to 2020?…
Gruja
  • 107
0
votes
2 answers

Proof Fermat's Little Theorem

I'm trying to follow the proof for here https://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html?fbclid=IwAR2WAws38n6M--Dx4cOWc8QToKG9sJf1JL9V_9MDATTG4UIx2yNyvpF2M7Q I'm a bit confused by the part Suppose that ra and sa are the same modulo p,…
johnnyB
  • 45