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
1 answer

A question about properties in modular arithmetic

Some time ago, I posted a question on six primes numbers forming an arithmetic progression, and someone commented the following: " Let $m$ and $n$ be positive integers with $\gcd(m,n)=1$. Then the sequence $m,2m,3m,…,nm$ when taken mod $n$ will give…
Vmimi
  • 979
1
vote
2 answers

Computing linear congruence

I have the following linear congruence: $$40x\equiv 28\pmod{73}$$ I have attempted to simplify the congruence by dividing both terms by 4, $$10x \equiv 7\pmod{73}$$ but I can't figure out what to do next. What would be the best method around…
1
vote
1 answer

Modular Arithmetic

Possible Duplicate: Modulo Arithmetic How would you find x in a modulo arithmetic expression x^e mod p knowing only e and p? e is an integer, 0 ≤ e < p, that is relatively prime to p-1; and x is an integer, 0 ≤ x < p.
user8442
1
vote
1 answer

What is the length of this sequence?

Let $m>1$ be a prime number, and $k$ and $B$ be arbitrary elements of $\{0,1,\ldots , m-1\}$. Let $A\in \{0,1,\ldots , m-1\}$ such that $\gcd(A,m)=1$. For the following definition we use $\mod{m}$ to denote an operation and not an equivalence class.…
1
vote
1 answer

Is there any relationship between remainder obtained through modulo 2 binary division and remainder obtained in a normal decimal division?

For some cases, modulo 2 binary division is giving the same remainder as a base 10 modulus but for some cases it is not. Is there some relationship between the two remainders? Example:- 1.) q = 101000110100000 p = 110101 modulo 2 binary division…
Krash
  • 111
  • 3
1
vote
1 answer

Modular arithmetic in Montgomery form

I am trying to apply an algorithm that requires significant modular arithmetic, but in such a way as to avoid as many costly mod or division operations as possible. I found the Montgomery multiplication method and its form of integer residues (via…
1
vote
1 answer

Find r and n in congruence $827. 3^{839} ≡ r \mod n$

Edit: Find r and n in congruence $827. 3^{839} ≡ r \mod n$ I am new to this modulo arithmetic topic and was given a question to solve. Find $n$ in the following equation: $$3^{839}\equiv827\bmod n$$ I have tried finding $3^{128}$ and thought of…
coffee
  • 61
1
vote
1 answer

How to prove there is at most one remainder then there is at least one remainder

In equation $b=aq_1 + r_1$ and $b=aq_2 + r_2,\;\;$ I have proof $r_1 = r_2$ (there is at most one remainder). But how to proof there is at least one remainder? Let $S = \{s\in \mathbb Z, s \geq 0 : \exists q \in \mathbb Z \text{ such that } b = aq +…
1
vote
2 answers

Modular arithmetic: confusion one the $mod$ operator.

Suppose I have $a\equiv b \text{ (mod $c$)}$ and I just know $c$. I want to know, say $b$. Is this the same as $a$ mod $c$? If so, why? I think I confuse the congruence with the equality symbol, because only recently I learned that sometimes $mod$…
Barbra.
  • 25
1
vote
2 answers

Modular arithmetic - integer's remainder computed iteratively

When reading about Rabin-Karp's algorithm for substring search I've found that, for example: $312 \bmod 13$ can be calculated also as: $[10*([10*([10 * 0 + 3] \bmod 13) + 1] \bmod 13) + 2] \bmod 13$ How can I prove that's correct? What properties…
1
vote
1 answer

prove the equation $x^4 + y^4 + z^4 =3009$ has no integer solutions.

prove the equation $x^4 + y^4 + z^4 =3009$ has no integer solutions. I tried modulo 3 and find that it is possible that has integer solutions when $x,y,z$ are all congurent to 0 and 3009 is also congruent to 0 (mod3). And don't know where I get it…
1
vote
3 answers

What is different in calculating modulo prime and not prime number?

The basic modulo operations: $$(A + B ) \text{ mod } P = (A \text{ mod } P + B \text{ mod } P) \text{ mod } P\\(A - B ) \text{ mod } P = (A \text{ mod } P - B \text{ mod } P) \text{ mod } P\\(A * B ) \text{ mod } P = (A \text{ mod } P * B \text{ mod…
1
vote
2 answers

When is $(p^2-1)/8$ even?

I am trying to find for what values of p $\frac{p^2-1}{8}$ will be even number $\frac{p^2-1}{8}=2m\implies (p-1)(p+1)=8(2m)$ then can I write $p\equiv 1\pmod8$ or $p\equiv -1\pmod8$ ? Also trying to find for what values of p it will be an…
user529392
  • 49
  • 5
1
vote
2 answers

Finding the last nonzero digit of $30^{2345}$

3)Find the last non-zero digit of $30^{2345}$ $3^1=3$ $3^2=9$ $3^3=27$ $3^4=81$ $3^5=243$ ... as last digit is following a cycle of $4$ so $2345/4$ gives remainder of 1, and $3^1=3$, so the last non-zero digit is 3. This solution confuses me.…
1
vote
2 answers

Logic or meaning of $5 \equiv \frac{4}{8}\pmod {12}$

In modular division, what is the meaning that should be ascribed to the notation exemplified below (also given on p. 5 of this)? $$\begin{align} \implies & 5\cdot8 \equiv 4\pmod {12} \tag{i} \\[2ex] \implies & 5 \equiv \frac{4}{8}\pmod {12} \tag{ii}…
jiten
  • 4,524