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

learn more… | top users | synonyms

2
votes
3answers
113 views

How to find this expression $1000! \mod 3^{300}$

How to find this expression $(1000!\mod 3^{300})$?
3
votes
1answer
114 views

Finding number of solutions to an equation in $\mathbb F_p$

$p=3 \pmod 4$ is a prime. Let $b\in \mathbb F_p^*$. Show that the equation $v^2=u^4-4b$ has $p-1$ solutions $(u,v)$ with $u, v \in \mathbb F_p$. If we write the given equation as $v+u^2=x$ and ...
3
votes
4answers
202 views

Prove that $2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$

I am utterly new to modular arithmetic and I am having trouble with this proof. $$2222^{5555}+5555^{2222}=3333^{5555}+4444^{2222} \pmod 7$$ It's because $2+5=3+4=7$, but it's not so clear for me ...
7
votes
2answers
167 views

How many solutions does $x^2 \equiv {-1} \pmod {365}$ have?

How many solutions does $x^2 \equiv {-1} \pmod {365}$ have? My thought: $365 = 5 \times 73$ where $5$ and $73$ are prime numbers. So we can obtain $x^2 \equiv {-1} \pmod 5$ and $x^2 \equiv ...
4
votes
6answers
116 views

Solve $91x\equiv 84\pmod{147}$

So, I posted a similar question to this, and I know that the equation is solvable because $\gcd(91,147) = 7$ and $7 \mid 84$. Plugging into Wolfram Alpha, I found that the solution is a line $21n + ...
4
votes
2answers
55 views

Easy way to compute $k^{20}=1\pmod{101}$?

I know that it is assumed hard to calculate the opposite ($20^k$), basically the discrete log problem. I also know that is easy to verify for some $k$ whether $k^{20}=1\pmod{101}$ holds. Solutions are ...
5
votes
6answers
267 views

Show that $x^4 +1$ is reducible over $\mathbb{Z}_{11}[x]$ and splits over $\mathbb{Z}_{17}[x]$.

Reduction into linear factors $\mathbb{Z}_{17}[x]$: This part is not too hard: $x^4 \equiv -1$ mod 17 has solutions: 2, 8, 9, 15 so $(x-2)(x-8)(x-9)(x-15) = x^4 -34 x^3 +391 x^2-1734 x+2160 \equiv ...
0
votes
1answer
234 views

Find all solution of a Quadratic Congruence

Find all solution of $x^2 \equiv a \pmod {11^2}$, for every $a \in Q_{11}$. I'm not sure what's the question actually asking. Do I need to find all the quadratic residues of $\pmod {11^2}$ or ...
2
votes
4answers
105 views

Proving $x$ is divisible by $20$

I need to prove that $x$ divisible by $20$ if and only if $x=0\pmod4$ and $x=0 \pmod 5$ proving that if $x=0 \pmod 4$ and $x=0 \pmod 5$ than $x$ divisible by $20$ is by the Chinese theorem (am I ...
0
votes
4answers
59 views

Prove $2^k+1$ divisible by 3 for odd K

Prove $2^k+1$ divisible by 3 iff $k$ is odd number. Since I need to prove both direction looks like if I need to prove it's divisible by 3 it's by induction and the other side by congruence..am I ...
1
vote
3answers
124 views

Gcd, Fermat little theorem and Euler function

Hi im stuck with two question: (1). Prove that if $a^{n-1} = 1 \pmod n$ than $a$ and $n$ are relatively prime. looks like Fermat little theorem but I know this theory works on prime numbers so I ...
1
vote
0answers
125 views

Order of kernel of a homomorphism

Let $p,q$ be distinct primes. Prove that the kernel of the map $$f: (\mathbb{Z}/p^k\mathbb{Z})^* \rightarrow (\mathbb{Z}/p^k\mathbb{Z})^*$$ defined by $f(x)=x^q$ has order $\gcd(p-1,q).$ Thank ...
5
votes
2answers
172 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
0
votes
2answers
414 views

How to factor a polynomial modulo p?

Is there a general strategy to factoring a polynomial modulo p? I've looked on Google but I've had a hard time finding anything that specifically outlines an approach that I can understand.
0
votes
5answers
187 views

Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$

Can you please help me a bit with this question? How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$? Thanks a lot!
3
votes
3answers
189 views

How to compute $\mathbb{Z}_n^*$, the unit group of the integers modulo $n$?

I am trying to wrap my head around calculating residue classes, for example $\mathbb{Z}^*_{12} = [1]...$ Would anyone mind making up an example with a decent explanation. I just wrap my head around ...
4
votes
4answers
105 views

What prerequisite knowledge is needed to understand “Multiplicative group of integers modulo n”

I want to self teach myself Multiplicative group of integers modulo n since it's a foundation in cryptography, IT Security, and Microsoft's UProve technology. When I go to the Wikipedia page I am ...
13
votes
2answers
353 views

Find a composite number $n$ satisfies $(2+3I)^n≡2-3I\pmod{n}$

As we know if $p$ is an odd prime number then $$(a+bI)^p\equiv a+(-1)^\frac{p-1}2bI\pmod{p},$$ where $I=\sqrt{-1}$. However, is there any composite number $n$ that satisfies ...
4
votes
1answer
3k views

Rules for algebra equations involving modulo operations

While working on a menial task in front of a clock today I was distracting myself by proving that all three hands only align twice a day. That lead me to wonder how one would deal with more complex ...
0
votes
1answer
47 views

Can this function with modulo and truncated division be simplifed?

Can this function with modulo and truncated division (DIV) be simplifed? f(x)=(x%c)*r+DIV(x,c)%r Basically, I use this ...
1
vote
5answers
710 views

Solutions of the congruence $x^2 \equiv 1 \pmod{m}$

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$. Thanks.
3
votes
9answers
910 views

Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$

Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$. I believe this might be tried using division algorithm, or modular arithmetic. I don't see exactly how to start this... Please help.
0
votes
1answer
86 views

Proving there is an $a$ that is not a quadratic residue mod $p$ for any prime $2 < p \leq 1000$

Prove there is an integer $a$ such that for all primes $p$ between $2$ and $1000$, the number $a$ is not a quadratic residue mod $p$. Thanks.
0
votes
3answers
260 views

Showing that the GCD of two expression multiplied by n, for any n

Can you please help me with this question: Show that the gcd of $8n+7$ and $7n+6$ is $1$, where $n$ is a positive integer. Thank you.
0
votes
3answers
247 views

Finding the remainder after dividing $2^{2^{17}} + 1$ by $19$

Can you please give me any hints for finding the modulo of the division of $\large \displaystyle 2^{2^{17}} + 1$ with the number $19$. Thank you.
0
votes
3answers
96 views

Find the solutions of system of equivalences for modulo

Can you please help me solve the system of equivalences: $x \equiv 3 \pmod {13}$ and $x \equiv 3 \pmod {17}$ and $x \equiv 13 \pmod {23}$ Thank you!
2
votes
5answers
285 views

Finding solutions of the system $27x + 90 \equiv 18 \pmod{99}$

I have to find solutions for the expression $$27x + 90 \equiv 18 \pmod{99}$$ My only problem is that I can only solve expressions like $ax \equiv b \pmod{n}$. How can I get rid of the $90$? ...
0
votes
1answer
391 views

inverse modulo calculation

Let n is divisible by m, and we have to find $V=\frac{n}{m}(mod)p$... In case if we know the value of $n(mod)p$,$m(mod)p$ not n,m how can we find $V$ ????? I know we can find answer by evaluating ...
1
vote
2answers
59 views

How to reduce a congruence to a “unique” solution?

I have to find a value for $r$ such that it is within the bounds of a modular equation. For example: $$2381\equiv r\mod{87}$$ So I need to find $0\leq r<87$. How can I do this? The notes I took ...
0
votes
4answers
99 views

Polynomial division in $\mathbb{Z}_n[x]$

For which value of $n$ is $x^3-x$ divisible by $2x-1$ modulo $n$?
1
vote
1answer
484 views

Reverse mod operation getting bounded number

Is it possible to get the reverse of the mod operation if I just want the first possible number? I mean, if I can bound the initial number. For example: I want to do $(x+y) \pmod {10} = z$ ($x$ ...
0
votes
2answers
162 views

Solving Chinese Remainder Theorem [duplicate]

If $x = am + k = bn - k$ for known $a,b,k$ and $gcd(a,b)$, how to solve for $x$ using Chinese Remainder Theorem?
1
vote
1answer
336 views

Affine cipher - Modular multiplicative inverse

I want to decrypt an Affine cypher. Definition: a^-1(c-b) a = 5, b = 13 Range: Alphabet (26 letters) Letter to decrypt: K (c = 10) So: = 5^-1(10-13) = 5^-1(-3) I am not sure what do to next. ...
0
votes
2answers
59 views

show that if $g \cdot b \equiv 1 \pmod n$, then $b$ is also a primitive root of $U_n$ [duplicate]

Show that if $g$ is a primitive root of $U_n$ and $g \cdot b \equiv 1 \pmod n$, then $b$ is also a primitive root of $U_n$. What property of primitive root should I use? How about $g \in U_n$ is a ...
2
votes
1answer
68 views

Factoring of exponents in Simon's algorithm

In derivations of Simon's algorithm (e.g., p. 4), it's often meant to be apparent that $$(x_0\oplus s)\cdot y=(x_0\cdot y)+(s\cdot y)$$ where $\oplus$ is "direct sum modulo 2", $x_0,s,y$ are all ...
2
votes
1answer
146 views

Inverse of integer power in modulo ring

For a prime $n$ and a generator $g$ of the multiplicative Group $\mathbb Z/n\mathbb Z$, $b = g^a \mod n$ is a bijection for $a \in \{0,\dotsc,n-2\}$ and $b \in \{1,\dotsc,n-1\}$. But how can I ...
1
vote
3answers
141 views

Why are these two equivalent? (Modular multiplicative inverse)

According to Wikipedia's entry "Modular Multiplicative Inverse," $d\equiv e^{-1} \pmod {\phi(n)}$ and $ed\equiv 1 \pmod{\phi(n)}$ are equivalent. Why is this the case? Can someone provide a ...
1
vote
1answer
37 views

Modular arithmetic proof

If $a\equiv b \pmod {m_i}$, $1\leq i\leq k$, there $m_1,m_2,\dots,m_k$ relatively prime, then $a\equiv b\pmod{m_1m_2\cdots m_k}$ My attempt: $$\frac{a-b}{m_i}=t_i, t_i\in Z$$ ...
3
votes
2answers
456 views

What does it mean to “have a multiplicative inverse of modulo 10!”?

Here's the question: What's the smallest integer > 1 that has a multiplicative inverse modulo 10! (that is, 10 factorial)? What does that mean? I understand that: We say that x is the ...
3
votes
4answers
106 views

Find all solutions of $x^8 \equiv 5 \pmod {3\cdot 11}$

Find all solutions of $x^8 \equiv 5 \pmod {3\cdot 11}$ Im not sure should I use primitive root or quadratic residue. For primitive root, $U_{33} = ...
2
votes
4answers
93 views

Find all solutions of $7x^2 \equiv 1 \pmod {17}$

Find all solutions of $7x^2 \equiv 1 \pmod {17}$ I found out all the primitive root of $U_{17}$ to be : $\{3,5,6,7,10,12,14\}$. To continue with the computation, I think i need to use the theorem ...
5
votes
2answers
55 views

Is it a valid step while solving modular arithmetic equation?

It's probably a very basic question. Is this equation $$91x\equiv21\pmod{56}$$ equivalent to $$35x\equiv21\pmod{56}$$ If so, then what property says that these equations are equivalent?
3
votes
2answers
342 views

Linear equation system in modular aritmetic

Can someone explain me how to solve linear equation system in modular aritmetic when i have less equations than variables. I need algorithm for this, something with gaussian matrix maybe. $$4x_1 - ...
3
votes
1answer
97 views

Equation mod $p$

How many non-trivial solutions does the equation $$a^2+b^2+c^2=0$$ have in $\mathbb{F}_p$? By non-trivial, I mean all solutions $(a,b,c)\ne (0,0,0)$. I've checked for small $p$, and seem ...
2
votes
0answers
36 views

For which minimal $k$ true is that ${4}^{k}\cdot n\leq \displaystyle\sum^{n}_{i=1}{a}_{i}^{k}\leq {5}^{k}\cdot n$, ${a}_{i}\in {1,2,3,4,5,6}$?

I've got the following inequality, which bounds Minkowski distance. ${4}^{k}\cdot n\leq \displaystyle\sum^{n}_{i=1}{a}_{i}^{k}\leq {5}^{k}\cdot n$ and values of ${a}_{i}\in {1,2,3,4,5,6}$ We know all ...
0
votes
1answer
65 views

Some analogue of the Chinese Remainder Theorem

I have mutually coprime numbers $p_1,\ldots,p_n$ and three collections of numbers $i_1,\ldots,i_n$, $j_1,\ldots,j_n$, $r_1,\ldots,r_n$ such that $0 \leqslant i_k, r_k < p_k$ and $0 < j_k < ...
2
votes
3answers
136 views

Modular homework problem

Show that: $$[6]_{21}X=[15]_{21}$$ I'm stuck on this problem and I have no clue how to solve it at all.
1
vote
1answer
114 views

How to solve exponential format modular equation have the same base

I'm reading the paper of Taher Elgamal whichs talks about his digital signature scheme. For example a user needs to sign a document $m \in [0, p-1]$ where $p$ is a large prime number. His private key ...
2
votes
2answers
125 views

How can there be two products with same remainder when divided with 100

For $a_i,b_j \space \epsilon \space \space \{ 1..100 \} ,\ i \neq j$ ,how can we prove that there exists two products with same remainder $a_i * b_j \space mod \space 100$ . ie $a_1*b_1 mod \ ...
1
vote
1answer
291 views

If $p \equiv 1 \mod{4}$ is prime, how to find a quadratic nonresidue modulo $p$?

If $p \equiv 3 \mod{4}$ is prime, then $-1$ is a quadratic non-residue modulo $p$. This is not the case when $p \equiv 1 \mod{4}$. How can we find a quadratic non-residue in this case? At least one ...