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

Filter by
Sorted by
Tagged with
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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$....
1
vote
0answers
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 ...
0
votes
0answers
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, ...
0
votes
1answer
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 $?$
-1
votes
1answer
17 views

The quotient remainder theorem [duplicate]

I have tried understanding how to solve questions of these type using pen and paper, without access to a calculator. Here's the question: What is the remainder of $2019^2 + 2019^4 + 2019^6 + 2019^...
6
votes
3answers
216 views

Isn't 1 congruent to -1?

I have read something about Wilson's theorem, but I found that $$(n-1)!\ \equiv\ -1 \pmod n$$ I thought, that $-1\equiv 1\pmod x$, but in all literature, I only found upper theorem. My reason why I ...
1
vote
2answers
19 views

Suppose that $a \equiv b\mod m$ and that $a \equiv b\mod n $ .Assuming gcd$(m;n) = 1 $ ,prove that $a \equiv b\mod mn$ [duplicate]

How should I approach this question? I was thinking of splitting it up such as as $ mt=b$ and $ax + ny=b$
5
votes
3answers
70 views

Computing $\gcd\{n^k - n^\ell : n \in \mathbb Z\}$

Computationally, it is possible verify that $n^8 - n^2$ is divisible by $252\ (= 2^2\cdot3^2\cdot7)$ for every $n \in \mathbb Z$. One crude way of doing so is by looking at the sequence $$ (\...
1
vote
2answers
68 views

Prove that $(p-2)! \equiv 1\mod p$ without using Wilson's Theorem.

This question is from a previous exam paper that I am using to revise. As per the rules of the School of Maths and Stats in my university they are not allowed to give out solutions to previous exams. ...
0
votes
2answers
40 views

Prove $gcd(m,n)=p\implies Φ(mn)=(p/p-1)Φ(m)Φ(n)$

I know that if $gcd(m,n)=p$, then both $m, n$ have $p$ as a factor. I also know that for any prime $p$, $Φ(p)=p-1$.
-1
votes
1answer
51 views

Prove $a^{(p-1)!}\equiv1 \pmod p$. [duplicate]

If $p$ is prime and $a$ is a positive integer where $p\nmid a$, then prove $a^{(p-1)!}\equiv1 \pmod p$. I know that Fermat's Little Theorem guarantees that $a^{p-1} \equiv 1 \pmod p$. I also know ...
1
vote
1answer
28 views

Prove or disprove if ma ≡ mb (mod n), then a ≡ b (mod n) for all positive integers a, b, m, n. [duplicate]

How can I prove/disprove if ma ≡ mb (mod n), then a ≡ b (mod n) for all positive integers a, b, m, n. I know the fact that ...
0
votes
0answers
13 views

Modular regression model

Short version, I need to find a regression to this : $ a\equiv t\pmod \Delta $, $a$ and $\Delta$ are the unknowns constants. Any idea where I should start looking ? Some context, because I may be ...
0
votes
0answers
46 views

Calculate $a^b \mod c$ [duplicate]

Let's say we have the expression $a^b \mkern-10mu\mod\! c$ and $b$ is really large, e.g. $37^{165}\mkern-10mu\mod 65$. How to work this out by hand? There's a way to avoid the large exponent.
3
votes
2answers
95 views

Proving systems of nonlinear modular equations have no solution

I have reason to suspect this system of six nonlinear modular equations has no solution for $2 < x < y < z$ even integers. $$ \left\{ \begin{aligned} z(3y+2) \equiv y(3z+2) \equiv 0& \mod ...
0
votes
3answers
82 views

Does exist an efficient algorithm to solve the equation $\ ax^2-cy-d=0$?

Given the Diophantine equation: $\ ax^2-cy-d=0$ , the coefficients $\ c$ and $\ d$ are numbers in range of $\ 10^{300} $. Does exist an efficient way to find solution for it?
0
votes
1answer
67 views

Prove $x^{x^x} \equiv x^x \mod 16$

$x^{x^x} \equiv x^x \pmod{16}$ Prove by a simple and (quite an) elementary proof that the expression above is true for every $x>2$ ($x$ is a natural number). The question does not have a topic and ...
0
votes
4answers
61 views

how to calculate remainder of large numbers? (no calculator)

How do I calculate the remainder of $30^{29} \pmod {51}$? I cant use Fermat's little theorem since $51$ is not a prime number.
0
votes
0answers
23 views

Why does ElGamal Signature works

I wanted to know if there is an specific "why" about why does the ElGamal Signature Scheme work. I'm already aware that it works because of asymetric key. But don't really get the maths behind it. ...
1
vote
0answers
40 views

Prove that the system $x\equiv a(\text{ mod }m)$, $x\equiv b(\text{ mod }n)$ has a solution iff GCD$(m,n)\ |\ (a-b)$ [duplicate]

My assignment is the following: Prove that the system $$x\equiv a\ (\text{mod }m)$$ $$x\equiv b\ (\text{mod }n)$$ has a solution if and only if GCD$(m,n)\ |\ (a-b)$ My approach is the following: [$...
2
votes
1answer
50 views

Find all solutions of the congruence $x^3 - 3x + 2 \equiv 0 \pmod {25}$

I know that the above problem is equivalent to: $x^3 - 3x + 2 \equiv 0 \pmod {5^2}$ So: Let $f(x) = x^3 - 3x + 2$ and $f'(x) = 3x^2 - 3$ Solve for: $f(x) = x^3 - 3x + 2 \equiv 0 \pmod {5}$ -> $x_1 ...
1
vote
1answer
40 views

Prove that a recurrence for Rule 30 is: B2=MOD(A1+B1+(1+B1)*C1,2)

Prove that Rule 30 satisfies the recurrence: $$T(1, k) = [k = N]$$ $$T(n,k)=(T(n-1,k-1)+T(n-1,k)+(T(n-1,k)+1) T(n-1,+1+k)) \bmod 2$$ where [ ] is the Iverson bracket. ...
0
votes
2answers
122 views

Let p be a prime number, show that if p ≡ 1 mod 3, then p ≡ 1 mod 6

I have the following assignment: Let $p$ be a prime number, show that if $p\equiv_{3}1$, then $p\equiv_{6}1$ I am having trouble making an approach to the solution.I appreciate any help. I can´t make ...
0
votes
0answers
11 views

How to do bitshifts and masking for Montgomery multiplication with redundant form

I'm implementing 1024 bit Montgomery multiplication using redundant form words, where each word is 32 bits and has 1 extra redundant bit. I understand multiplication in this form so I don't have to ...
0
votes
1answer
56 views

Finding the maximum or minimum of two numbers using mod

To find the maximum of two coprime positive integers $a,b$: $$\frac{ab \left[(a \bmod{b}) \bmod{a}) + ((b \bmod{a}) \bmod{b})\right]}{(a \bmod{b})(b \bmod{a})}=\max(a,b).$$ From this, you can also ...
-1
votes
1answer
22 views

An algorithm to solve an equation with modulo?

given $(2n + 1) \mod k = n \mod k $ where $k$ is known what's an algorithm to find $n$ ?
2
votes
1answer
50 views

Congruences with twin prime numbers

Let $p$ and $q$ be a pair of twin primes, such that $q = p + 2$. Prove the following: $\exists$ an integer $a$ such that $p \mid (a^2 - q)$ $\iff$ $\exists$ an integer $b$ such that $q \mid (b^2-...
0
votes
1answer
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 =...
-1
votes
3answers
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 ...
2
votes
4answers
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
0
votes
3answers
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}$$
0
votes
1answer
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}$$
-2
votes
3answers
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$.
2
votes
1answer
70 views

If $a+b = 2020$ and $ab$ is a multiple of $2020$ , find all pairs of $(a,b)$

If $a+b = 2020$ and $ab$ is a multiple of $2020$ , find all pairs of $(a,b ) $ for $a,b \in \mathbb N.$ My take : $$2020a-a^2 = 2020k$$ $$a = \dfrac{2020 \pm \sqrt{2020^2 -4\cdot2020k}}{2}$$ Since $...
0
votes
0answers
19 views

Find all subfix $n$

$a \ge 2$, $a_0=1$, $a_1=a$, $a_2=2a^2-1$, $\frac{a_{n+1}}{a}=a_n+2aa_{n-1}-a_{n-2}, \forall n \ge 2$. Find all subfix $n$, such that there exists such integer $a$, satisfying , among all $a_k \equiv ...
3
votes
0answers
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$...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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, ...
0
votes
2answers
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 ...
1
vote
2answers
40 views

Modular Arithmetic: Problem with the calculation

I am trying to solve the following: ...
1
vote
0answers
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
3answers
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)+...
-1
votes
2answers
89 views

Why are there no impossible modular residues of cubes for some moduli?

I was working on a problem about cubes but I kept on getting stuck on some cases because for some moduli, for example 10, there are no impossible residues. For modulo 10: \begin{array} .N & N^3\...
2
votes
0answers
60 views

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