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

Find the modulo between two large number

I'm trying to find 3185^2753 mod 3233 to decode a RSA message. How can I do it? What is the theorem behind this, if any? The original question is: What is ...
5
votes
1answer
493 views

Find the inverse modulo of a number

I'm trying to find the inverse modulo of $17\pmod{3120}$ I've tried: $$ \begin{eqnarray} 3120 =& 17\cdot 183 &+ 9\\ 17 =& 9\cdot 1 &+ 8\\ 9 =& 8\cdot 1 ...
2
votes
1answer
120 views

How to compose given add, sub, mult, div functions to map an integer M to N?

Given six integers ($M$, $N$, $a$, $b$, $c$, $d$), is it possible to create a function $H$ such that $H(M) = N$, with the restriction that $H$ is a composition of the following four functions (which ...
1
vote
0answers
88 views

Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations

Legendre Symbol, find the value of $\frac{p}{q}$ for all combinations of $p=7,11,13$ and $q=227$ My thought: $(7, 227)$ are distint odd primes, same for $(11,227)$ and $(13, 227)$ thus, ...
2
votes
1answer
102 views

congruence modulo infinity

Going through Hensel's Lemma, I feel I read somewhere that the limit of sequence of integers $a_0,a_1,a_2,...$=$ a$ is root of the $f(X)\in\mathbb{Z}_p[X]$, where, ...
4
votes
4answers
156 views

How to derive this expression $ r ^{ (p-1)/2} \equiv -1 \pmod p$ for primitive root of an odd prime $p$.

While studying Elementary Number theory by David M. Burton I came across this line: because $r$ is a primitive root of $p$, $$ r ^{ (p-1)/2} \equiv -1 (\mod p) $$ where $p$ is an odd prime. ...
1
vote
1answer
104 views

Matrix inversion help

If $g(n)$ is an integer functions periodic in $a$ And $\phi(a)$ is eulers totient function And $[r_1,r_2,r_3,...r_{\phi(a)}]$ are the postive integers less then $a$ coprime to $a$ With ...
2
votes
3answers
114 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
203 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
168 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
272 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
236 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
128 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
126 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
429 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
198 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
48 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
731 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
953 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
262 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
248 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
395 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
507 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
163 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
360 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
148 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
144 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
467 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
107 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
56 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
350 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 - ...