# 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$.

9,931 questions
Filter by
Sorted by
Tagged with
16 views

### Finding all solutions to a system of congruence equations

Find all $a,b\in \{0,1,2,\ldots\}$ such that \begin{align} a+4b\equiv 0 \pmod{5} \\ a+b\equiv 1 \pmod{2} \end{align} I've found that e.g. $a = 5, 15, 25,\ldots$ and $b=0$ works, but I'm unsure how to ...
15 views

### What other residues do semiprimes hit?

One result from Goldbach's conjecture, is that any $p,q$ that sum to $2n>6$, create a semiprime that is congruent to the negative of a quadratic residue mod $n$. What other residues do semiprimes ...
25 views

### Solving equations in groups (mod $n$)

Solve the equation $2x=0$ in group $\Bbb Z/10\Bbb Z$. I’m new with the concepts of modular arithmetic and I am having some trouble in knowing what should I do to solve this problem. Can someone give ...
22 views

### Understanding proof of $a\equiv b\pmod{n}\implies r_n(a)=r_n(b)$ [duplicate]

Prove that $$a\equiv b\pmod{n}\implies r_n(a)=r_n(b),$$ where $r_n(h)$ means the remainder of $h$ in the division by $n$. I have seen this proof: By the division algorithm, $a=qn+r_a$ and $b=cn+r_b$....
41 views

### Modulus system of equations and modular arithmetic.

Let $r \in \mathbb{R}$ such that $-82 < r < 82$. Let: $p_1 = r/44$ $p_2 = r/42.8$ $m_1 = 21p_1$ $m_2 = 21p_2$ Given $p_1 \pmod 1$, $m_1 \pmod 1$, $m_2 \pmod 1$ solve for $r$. As pointed ...
12 views

### proving or disproving property of subspaces over modulo field.

I need to prove or disprove the following statement: "If $V$ is a vector space over $Z_p$ where $p$ is prime, then any nonempty subset of $V$ that is closed under addition is a subspace of $V$." Now, ...
35 views

### Equality in Modular Congruence: $a\equiv b\pmod p$ implies $a=b$ [closed]

Given that $a ≡ b \mod p$ and that $a$ and $b$ are drawn from the set $\{ 1, 2, \dots, p-1 \}$ Is $a$ guaranteed to be identical to $b \,?$ And if yes, why $?$
17 views

50 views

35 views

### How to do division of two numbers which are already under modulo 'm'? [duplicate]

How to do division for the following example? Case 1 : Without modulo n1 = 40, n2 = 8 Quotient = n1/n2 = 5 Case 2 : With modulo m = 6 n1 = n1 mod m = 4 (AND) n2 = n2 mod m = 2 Quotient = 4 / 2 =...
52 views

### Why does $(g^b \bmod m)^a \bmod m = (g^a \bmod m)^b \bmod m$?

I have been trying to understand why the diffie hellman key exchange algorithm works, specifically why the two exponents can be swapped in it without the result changing. So my specific question is ...
98 views

### If $m \equiv 5\mod 10$ prove that $1991 \mid 12^m + 9^m + 8^m + 6^m$

I tried to find the remainder of each one of $12$,$9$,$8$ and $6 \mod 5$ and then combine them but I didn’t get the answer
73 views

### how to find multiplicative inverse in a Galois field?

How to find the multiplicative inverse of $$x^2+1 \pmod{x^4+x+1}$$
49 views

### how to solve this kind of modular arithmetic problems with exponents?

What is the method of solving similar problems like given below $$x^7 \equiv 25\pmod{54}$$
65 views

### Prove $k \equiv (-1)^n \bmod p$

Let $n$ be a positive integer. Let $p$ be a prime number. Define $k = \frac{(np)!}{n!p^n}$ Prove $k$ is a positive integer and $k$ $\equiv$ $(-1)^n\bmod p$.
70 views

38 views

### $x^2 \equiv a \mbox{ } \mbox{mod} \mbox{ } p$ has solution $x$ $\Leftrightarrow a^\frac{p-1}{2} \equiv 1\mbox{ } \mbox{mod} \mbox{ } p$

One of my friends asked me how to solve the following exercise: Let $p \geq 3$ prime. For every $a \in \mathbb{Z}_p^{*}$ it holds: $$x^2 \equiv a \mbox{ } \mbox{mod} \mbox{ } p$$ has a solution $x$...
23 views

### $∀n \in ℤ, p \in primes: n^2 \equiv 1 (\text{mod }p) \implies n \equiv 1 (\text{mod }p) \vee n \equiv −1 (\text{mod }p)$ [duplicate]

I have the following lemma which I'm required to prove. $∀n \in ℤ, p \in primes: n^2 \equiv 1 (\text{mod }p) \implies n \equiv 1 (\text{mod }p) \vee n \equiv −1 (\text{mod }p)$ I can see that ...
34 views

### Modular Exponentiation $a^n \bmod10$ for $a=\{2,3,…,9\}$

$a^n\bmod 10\;$ for $a=\{2, 3,..., 9\}$ For $a=3,7,9$ I can use Euler's theorem but what about the rest. I can see the patterns but how can I use those patterns as a proof? Note: I can't ...
56 views

### For equation $B^e \bmod M = X$, if all values except exponent $e$ are known, can an $e$ value that works be efficiently found?

For equation $B^e \bmod M = X$, if all values except exponent $e$ are known, can an $e$ value that works be efficiently found? I suppose if a low value of $M$ is used, it might be quite easy. But, ...
21 views

### Modular Arithmetic: What is the solution in this case? [duplicate]

I can't find the multiplicative inverse of 3? This is what I did. 6/3 * (MI of 3) (mod 6) 6/3 (mod 6) A= 3 B= ? M = 6 (A * B) % M = 1 (3 * B) % 6 =1 Some ...
40 views

### Modular Arithmetic: Problem with the calculation

I am trying to solve the following: ...
94 views

### Prove that given 17 integers, the sum of 9 of them is divisible by 9. [duplicate]

Prove that given any $17$ integers, there exist nine of them whose sum is divisible by $9.$ I'm pretty sure we have to use the pigeonhole principle, with the possible remainders as the pigeonhole, ...
29 views

### Multiple solutions for a monic degree-5 polynomial in $\mathbb{Z}_{5}[x]$ for which all elements of $\mathbb{Z}_{5}$ are roots

A monic degree-5 polynomial in $\mathbb{Z}_{5}[x]$ for which all elements of $\mathbb{Z}_{5}$ are roots I found is $(x^5 - x)$ since $f(1) \equiv$ 0(mod 5) $f(2) \equiv$ 0(mod 5) $f(3) \equiv$ 0(mod ...
34 views

### Explain negative modulo like I'm five?

I know this has been addressed here, but I confess to not fully understanding that, so I'm hoping someone can chime here. First, is there a canonical formula for this? In programming language ...
97 views

### Finding the last digit of $103^{103^{103^{103^{103}}}}$

I need to find the last digit of $103^{103^{103^{103^{103}}}}$ so the value in $\mod10$. I know \begin{align} 103^{103^{103^{103^{103}}}}&=(100+3)^{103^{103^{103^{103}}}}\\ &=100\cdot(stuff)+...
### What would a covering system for $x^2+1$ primes look like?
In trying to work on the question of whether there are infinite primes of form $x^2+1$, there's one issue I really don't get, and was hoping somebody might be good enough to help me out. Most of my ...