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

How to evaluate below expression of modular arithmetic?

How to evaluate (10^18)%(10^9 + 7) using modular arithmetic? How to proceed and what will be the steps?
Sakshi Singhal
1
vote
3 answers

Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.

Show that for any odd $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$. My workings so far: I proceeded by induction. Obviously $1^2 \equiv 1 \mod 8$. Then assume that for a certain uneven…
Slugger
  • 5,556
1
vote
2 answers

Problem with modular arithmetic quiz

Calculate $181^{-1} (mod\,29)$. As part of the calculation write $181 * A ≡ B (mod\,29)$ where $A \& B$ between 0 and 28. These are my calculations: $$181 (mod\,29) ≡ 7(mod\,29)$$ $$=>181^{-1}(mod\,29) ≡ 7^{-1} (mod\,29)$$ Because 29 is a prime…
1
vote
1 answer

Solving Linear congruence using backward substitution

Use the method of back substitution to find all integers $x$ such that $x ≡ 1 \mod 5$, $x ≡ 2 \mod 6 $, and $x ≡ 3 \mod 7$. Solution: The first congruence can be rewritten as an equality, $x = 5t + 1$, where $t$ is an integer. Substituting this…
Scarlet
  • 13
1
vote
3 answers

More elegant solution to $5^{5^5}$ mod 23

I needed to calculate $5^{5^5}$. This took about $5$ minutes or so using the standard trick of building the answer out of smaller answers. My method was this: Calculate $5^{25}=5^{23} 5^2$, which gives $10$, using Fermat's Little Theorem Calculate…
1
vote
2 answers

modulus question!!

I just have a question that is it: I want to know the equation that finds an unknown number which is a number that when we will mod it with 17 it is equal to 3 and when we mod it with 16 it is equal to 10 and when we will mod it with 15 it will…
1
vote
2 answers

Can the distributivity of the modulo operation be applied to only one operand of an addition?

It is known that $(a + b) \bmod n = [(a \bmod n) + (b \bmod n)] \bmod n$, but is it possible that the following are also true? $(a + b) \bmod n = [(a \bmod n) + b] \bmod n$ $(a + b) \bmod n = [a + (b \bmod n)] \bmod n$ I've been trying all sorts…
QCyrax
  • 13
1
vote
2 answers

Find all the possible $a,b$ in $a * b \equiv c \pmod{x}$

$$a * b \equiv c \pmod{x}$$ Where $a,b,c,x \in \mathbb{Z}$ and $0 < a \leq b < x; 0 < c < x$ What is the most efficient way to find all the possible $a,b$?
Ilya Gazman
  • 1,440
1
vote
0 answers

Minimum multiple such that two quantities have an integer between them.

I have two quantities $(nb-x)/a$ and $nb/a$ and I need to find minimum value of $n$ given $a, b$ such that $\exists k\in\mathbb Z$ for which $(nb-x)/a\le k
RE60K
  • 17,716
1
vote
2 answers

Last two digits of $529^{10}$

Trying to find out how to get the last two digits of $529^{10}$. I'm having trouble finding a good mod to reduce the $529$ down. Thanks.
1
vote
3 answers

Prove an implication in modular arithmetic

Prove for any integer $x$: if $x^{13} = 1 \mod \ 17$ then $x = 1 \mod 17$
OUCHNA
  • 429
1
vote
2 answers

Simple modular arithmetic question

Can someone please give a clear explanation on how from $(41)(59)x\equiv x\pmod {78}$ and $(41)(59)x\equiv 123\pmod {78}$ we get $x\equiv 123\pmod {78}$?
user60334
  • 717
1
vote
4 answers

Find the formula for calculating the number of integers congruent to n mod p between a and b inclusive where a,b are integers

As you read in the title, the goal is to find a formula that gives a number of integers congruent to n mod p between a and b. For example, if $(a,b)=(0,100)$, there are $51$ congruent integers $0$ mod $2$ between $0$ and $100$ inclusive. If…
1
vote
1 answer

Find the value of x such that $x \equiv -6 \pmod 5$

I have this question that is asking to find the value of x such that $x \equiv -6 (mod 5)$. I have worked out the answer but the answer is not in the choices available to pick. This is why I decided to post this question to get a second opinion to…
1
vote
2 answers

a divide b mod m when mod inverse doesn't exist

I am trying to compute [(2 ^ (2*n-1) + 1) / 3] mod m. The value for n can be very large, so computations are performed mod m. The computed value is always an integer, and hence the computation is valid for all m. When m is not divisible by 3, we…