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

Find the least multiplier of a fraction that gives a remainder of 1

I have two natural numbers $2\le b\lt a$. I want to know the least natural number $x_1$ such that $\frac{xa}{b}$ gives a remainder of $1$, and the least natural number $x_2$ such that the remainder is $b-1$ (I'm looking for a formula, not an…
ABu
  • 451
  • 2
  • 9
1
vote
0 answers

Express the modulo operation by sum when dividend is negative

I'm reading a section of the book Computer Systems: A Programmer's Perspective by Randal Bryant about integer arithmetic. There is the following definition: To better understand this quantity, let us define $z$ as the integer sum $z = x + y$, $z'$…
1
vote
2 answers

Find the modular residue of this product..

Please help me solve this and please tell me how to do it.. $12345234 \times 23123345 \pmod {31} = $? edit: please show me how to do it on a calculator not a computer thanks:)
MethodManX
  • 1,127
1
vote
2 answers

Counting the number of zeros yielded by modulo arithmetic functions

I have 4 functions \begin{align} f_1(x) &= x \text{ mod } 1\\ f_2(x) &= x \text{ mod } 3 \\ f_3(x) &= x \text{ mod } 4 \\ f_4(x) &= x \text{ mod } 12\\ \end{align} for $x \in [0,\infty) $ I want to create a function $g(x)$ that counts the number of…
1
vote
1 answer

Help with modular arithmetic

If$r_1,r_2,r_3,r_4,\ldots,r_{ϕ(a)}$ are the distinct positive integers less than $a$ and coprime to $a$, is there some way to easily calculate, $$\prod_{k=1}^{\phi(a)}ord_{a}(r_k)$$
Ethan Splaver
  • 10,613
1
vote
2 answers

Least residue power modulo

May someone confirm that the least residue of $44^8$ modulo $7$ is $4$ please? And that $2^2 \equiv 4\, (\!\!\!\mod 7)$? Thanks in advance.
1
vote
1 answer

How to create a modulo operator that changes?

Suppose I have the rule $$k \text{ mod } 2$$ Then $$0,1,2,3,4,5,6,...$$ produces $$0,1,0,1,0,1,0,...$$ I want to create a function that would allow me to do a sequence like 2-2-3 So I would have $$0,1,2,3,4,5,6,...$$ and this would…
1
vote
1 answer

How to calculate x mod (a b) if x mod a and x mod b are known

Suppose we have two relatively prime integers $a$ and $b$. Now, suppose that for some $x$ we have $x \equiv A \pmod{a}$ and $x \equiv B \pmod{b}$. Is there any way we can express $x \pmod{a \cdot b}$ in terms of $A$ and $B$? Also, can we do…
milin
  • 223
  • 1
  • 6
1
vote
1 answer

Is there any general criteria to find $e$'th roots modulo a primer number $p$?

It is known that if $p$ is an odd prime and $\gcd(e, p-1) = 1$, then one can easily find an $e$'th root of every $a \in \mathbb{Z}_p$ by computing $d \equiv e^{-1} \pmod{p-1}$: $$a^{de} = a^{k(p-1)+1} = (a^{p-1})^k a = a. $$ Also, if $e = 2$…
Bean Guy
  • 321
1
vote
1 answer

If we have a congruence a≡b (mod m), does it follow that a≡b(mod prime factor of m)

Consider a≡b (mod m) By the divison lemma, a = km+r (0
expl0it3r
  • 163
1
vote
1 answer

Why does $k \mid (p-1) /q$?

In M. Ram Murty's paper Artin's Conjecture on Primitive Roots I am not able to understand a statement. Let $k$ be the order of $a \bmod p$ where $p$ is a prime and also we have $a^{p-1} \equiv 1 \mod p$ then $k \mid (p-1)$ if $k \neq p-1$ then…
cabmetric
  • 181
  • 1
  • 9
1
vote
0 answers

About the solvability of a system of congruence

I am asking if there is any method to decide if the following system of congruence is solvable or not: $x_{1}$≡$a_{1}$ $mod (y_{1})$ $x_{2}$≡$a_{2}$$mod (y_{2})$ $x_{3}$≡$(a_{1}+a_{2})$$mod (y_{3})$ Here $y_{1},y_{2},y_{3}$ are not necessarily…
Safwane
  • 3,840
1
vote
1 answer

Find $x$ when $x^2\equiv y\bmod p$

Given $p$ is prime and $y$ is a constant. What's the fastest possible way to find $x$ where $x^2\equiv y\bmod p$? Example: $x^2\equiv97\bmod101$ would give us $x=81$ as one of the solutions. What's the fastest way to compute any one of the solutions…
1
vote
2 answers

Remainders problem

What will be the reminder if $23^{23}+ 15^{23}$ is divided by $19$? Someone did this way: $15/19 = -4$ remainder and $23/19 = 4$ remainder So $(-4^{23}) + (4^{23}) =0$ but i didn't understand it
user52950