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

$120^{1492}\pmod{100}$

How can I solve it? I can solve it using the fact: if $b\mid a$ then $b^{n}\mid a^{n}$ (I have proved it using induction) $\frac{120}{10}=12$ ,then $\frac{120^{2}}{100}$ this mean $120^{2}\equiv0\pmod{10}$ so, $120^{1492}\equiv…
Asaf
  • 131
1
vote
1 answer

Understanding Modular Arithmetic

Suppose that we are given: $$1124 \cdot 5097 \equiv x \mod 5693$$ Then $x = 1870$ since $(1124 \cdot 5097) -x = 5693k$ if $k=1006$. Is this correct? I'm not exactly sure how to think about these types of problems. It seems that I could simply do…
RedShift
  • 765
  • 3
  • 11
  • 28
1
vote
0 answers

Predicting a linear congruential generator (modular arithmetic)

I'm not an individual who majors in Mathematics nor am I intelligent. I'm just an average individual (average IQ) who likes to learn new things. Was playing monopoly and realized that the number shown after the dice was thrown COULD be…
David.L
  • 11
1
vote
2 answers

Find the remainder when $2^{2016}$ is divided by $47$

What is the remainder when $2^{2016}$ is divided by $47$? I have done Fermat's little theorem and I have now this: $2^{2016} \equiv 2^{38} \pmod{47}$ My issue is that $2^{38}$ is too large of a number to work with, how do I continue?
1
vote
0 answers

Modular Equations - filtering the solutions

I have a modular equation of the form: $$3^a N + c ≡ 2^d \pmod {2^{d+1}}$$ where $a$, $c$ and $d$ are positive integers and $c ≡ 1 \pmod 6$ or $c ≡ 5 \pmod 6$ I know that these equations produce numbers that cycle 1, 3, and 5 (in some combination)…
Ben Crossley
  • 2,544
1
vote
2 answers

Proving a statement using modular arithmetic

I keep running into the same type of failure when attempting to prove a statement using modular arithmetic, when the expression at hand is exponential. For example: Prove that the remainder of a power of $2$ divided by $6$ is either $2$ or…
barak manos
  • 43,109
1
vote
0 answers

Could we claim that the system has the only one solution there?

Given $$x_1>0,\quad x_2>0,\quad x_3>0,\quad x_4>0,\quad\textrm{and}\quad m>0,$$ could we claim that the system $$\begin{cases} [x_1+x_2]_m = 0 \\ [x_1+x_4]_m = 0 \\ [x_3+x_2]_m = 0 \\ [x_3+x_4]_m = 0 \end{cases}$$ has a solution only when $$…
alex
  • 11
1
vote
3 answers

Why is $15m=0\pmod {18}$ equivalent to $3m=0 \pmod {18}$?

$m$ is some natural number. Why is $15m=0\pmod {18}$ equivalent to $3m=0 \pmod {18}$? This is my question basically. I don't understand why that's true.
Matam
  • 301
1
vote
1 answer

How would I solve $n(a) := 3 1 7 2 a 6 3 7 5$ with $9|n(a)$?

$n(a) := 3 1 7 2 a 6 3 7 5$ What value needs a to be so that $9|n(a)$? Is there a way to solve this fast? My initial idea was to write it as a sum like $5 + 7 * 10 + 3 * 100 + 6 * 1000 + a * 10000 ... $ Because $a + c = b + d (\mod m )$ But this…
1
vote
1 answer

What does ''$p$ of order $10\mod 11$'' mean?

What does ''$p$ of order $10\mod 11$'' mean ? $p$ is a prime, what are then the possibilities for $p$ ?
user257
  • 989
1
vote
0 answers

Modular simple equation

Let's say I have three known numbers : $a$, $b$ and $m$. I want to find the smallest $x$ so that $a.x \equiv b\ (mod\ m)$ (the product of $a$ and $b$ is congruent to $b$ modulo $m$). In the cases where such an $x$ exists, is there a simple equation…
glmxndr
  • 333
1
vote
2 answers

Why does a = b (mod n) iff a - b is divisible by n?

I am specifically asking why the statement $a \equiv b \;(\bmod\; n)$ is equivalent to the statement $a = b + kn$, where k is some positive integer. Why is it that the difference of a and b has to be a multiple of n in order for them to have the…
Wesley
  • 1,567
1
vote
1 answer

How to calculate $(n^{-1})\%(p^a)$ for prime $p$?

I actually needed to calculate $(a/b)\%m$ when $m$ is not prime. Here is what I have done so far. $(a/b)\%m = (a* \text{modinv}(b))\%m$, I can calculate mod inverse only if $m$ and $b$ are co-primes. So, $m= p_1^{k_1} p_2^{k_2} \cdots…
Pranay
  • 11
1
vote
0 answers

Solving Modular Equation

Let $d$ and $n$ be coprime. What is the smallest positive solution for x in the equation: $$d^x \equiv 1 \mod n$$ This value must depend on both $d$ and $n$. We know that the maximum value for it is $\lambda(n)$ where $\lambda$ is the Carmichael…
1
vote
0 answers

What are good parameters for an $ax+b \pmod{2^L}$ hash with distinct first n bits of the first $2^n$ inputs?

I'm hashing 64 bit integers via $ax+b \pmod{2^{64}}$. Good parameters mean that, given an $1 \leq n \leq 64$, the first $n$ bits of the first $2^n$ inputs are distinct. How should I chose $a$ and $b$ to maximize the number of $n$ this applies…
mafu
  • 537