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

1
vote
1answer
364 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
471 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
353 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
66 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
130 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
295 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 ...
4
votes
5answers
162 views

How to find the values of $n$ for which $\displaystyle\underbrace{111\cdots1111}_{n}\equiv0 \pmod {41}$?

What are the values of $n$ satisfying $\displaystyle\underbrace{111\cdots1111}_{n}\equiv0 \pmod {41}$? I think $n=5k$, with $k=1,2,\cdots$, but I can't prove it.
0
votes
1answer
80 views

Solutions to system of congruences?

Say you have the following: $x \equiv a \pmod c$ and $x \equiv b \pmod d$, where $a$ and $b$ are known integers, and $c$ and $d$ are known positive integers. The following claim is made regarding ...
3
votes
1answer
49 views

Representing an element mod $n$ as a product of two primes

Given a positive integer $n$ and $x \in (\mathbb{Z}/n\mathbb{Z})^*$ what is the most efficient way to find primes $q_1,q_2$ st $$q_1q_2 \equiv x \bmod n$$ when $n$ is large? One option is just to ...
1
vote
1answer
185 views

Square root congruence equation: solving for the modulus

I'm trying to solve a system of the type $a^2 \mod n \equiv b\\ b^2 \mod n \equiv c\\ c^2 \mod n \equiv d\\ ...$ Where $n = p q$ for some primes $p$ and $q$. I know how to solve these systems ...
2
votes
3answers
263 views

Arithmetic series has first term

An arithmetic series has first term a and common difference d. The sum of the first 31 terms of the series is 310 a) Show that a + 15d = 10 b) Given also that the 21st term is twice the 16th ...
2
votes
1answer
56 views

Solve $x^{10} + 4x^3 +3x + 4 \equiv 0 \pmod {(4\cdot3)}$

Solve $x^{10} + 4x^3 +3x + 4 \equiv 0 \pmod {(4\cdot3)}$ Work: Let $P(x) = x^{10} +4x^3+3x+4 \equiv 0 \pmod 2$ and $12=4\cdot3=2^2\cdot3$ We have $P(x) \equiv0 \pmod {2^2}$ and ...
1
vote
2answers
145 views

Congruence equation mod $p$ involving the multiplicative order

Say $p$ is an odd prime s.t $p$ doesn't divide $x$. Let $x$ belong to the exponent $n$ modulo $p$. I need to show that if $n>1$, then $x + x^2 + ... + x^{n-1} ≡ -1 \mod p$ I'm not sure how to go ...
2
votes
3answers
1k views

How to find all the primitive roots in $\mathbb{Z}/49\mathbb{Z}$.

I need to find all the primitive roots of 49. First note, $ ϕ(49) = 42 $ Is there an easier way to go about trying all numbers less than $42$ to find the primitive roots of $49$ if we already know ...
-1
votes
1answer
91 views

Prove that in $\mathbb{Z}_p$, $[a]^{-1} = [a]$ if and only if $[a]=[1]$ or $[a]=[p-1]$

Let $p$ be a prime and a an integer. Prove that in $\mathbb{Z}_p$, $[a]^{-1} = [a]$ if and only if $[a]=[1]$ or $[a]=[p-1]$. I greatly appreciate your help on this question!
1
vote
2answers
160 views

Trouble with proof of Euler's theorem using Multiplicative Inverses

I am trying to understand a proof of Euler's theorem, namely the one that states $\gcd(a,n)=1 \implies a^{\phi(n)} = 1 \pmod n$. Here is how my teacher proved an important lemma that leads to the ...
1
vote
3answers
89 views

Modular Arithmetic

Can someone please explain why if: $15m+7 \equiv 4 \pmod 7$, then it is equivalent to saying $1m+0 \equiv 4 \pmod 7$? Thank you!
2
votes
4answers
135 views

Solving $13\alpha \equiv 1 \pmod{210}$

Determine $n \in \mathbb N$ among $12 \leq n \leq 16$ so that $\overline{n}$ is invertible in $\mathbb Z_{210}$ and calculate $\overline{n}^{-1}$. In order for $n$ to be invertible in $\mathbb ...
3
votes
4answers
90 views

Find the smallest $x$ for $9x \equiv 3 \pmod {23}$

$9x \equiv 3 \pmod {23}$ How to derive the smallest $x$. I understand I can use the extended euclidean algorithm for eg $19x = 1 \pmod {35}$. However, I not too sure how to work on it when it is $3 ...
2
votes
5answers
117 views

Solution of $19 x \equiv 1 \pmod{35}$

$19 x \equiv 1 \pmod{35}$ For this, may I know how to get the smallest value of $x$. I know that there is a theorem like $19^{34} = 1 \pmod {35}$. But I don't think it is the smallest.
1
vote
3answers
101 views

Evaluate $12^{23} \pmod {73}$

$12^{23} \equiv x \pmod{73}$ What is the smallest possible value of x? Having such a big exponent, it is difficult to use calculator to calculate. May I know is there any simpler way to do so?
1
vote
2answers
1k views

Inverse of a matrix mod 26

I'm trying to find the inverse of the matrix $\begin{bmatrix} 4 &8 \\ 5 &7 \end{bmatrix} \mod 26$. However the determinant of this matrix is 14 so I cannot use Cramer's rule and each time ...
4
votes
0answers
51 views

Prove that there are $736$ $2 \times 2$ matrices ($A$) where $A=A^{-1}$ [duplicate]

I'm doing some assignments to teach myself cryptology. I am still at the introductory cryptology level, where a lot of it is discrete mathematics, so I believe - and hope - that it is a somewhat ...
3
votes
2answers
69 views

A question about Modular arithmetic.

Determine the integers $n$ for which $\mathbb Z_n$, the set of integers modulo $n$, contains elements $x$ and $y$, such that $x+y=2$, $2x-3y=3$. Some help will be much appreciated, thank you.
0
votes
1answer
244 views

Finding modulus when all power of p are removed from N!

Given two integers $p$ and $N$. Let $m$ be number by $N!$ by max power of $p$ which divided $N!$. We have to find $m$ mod $p$. How to solve this?
4
votes
2answers
98 views

System of equations modulo primes

Is it generally possible to solve a set of linear equations modulo some prime numbers $\{p,q,r\}$. For example if I have the following congruences: $$ xa_p + yb_p \equiv d \pmod {p}\\ xa_q + yb_q ...
11
votes
5answers
318 views

Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
2
votes
1answer
81 views

Why is 2 not a Carmichael Number?

I know I'm missing something super basic here but: From the definition in my textbook, a Carmichael is any number n such that $(\forall a)\; \gcd(a,n) = 1$: $a^n \equiv a \pmod n$ or $a^{n-1} ...
3
votes
3answers
406 views

If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$

I was wondering if my proof makes any sense. $a \equiv b \pmod m$ $ m \mid a -b$ $ ml = a - b$ for some integer $l$ let $d = \gcd(a, m)$ let $c = \gcd(b, m)$ $$\frac{a}{d} = \frac{m}{d}l - ...
2
votes
3answers
82 views

How do I solve this congruency?

I have this congruence relation: 2013 ≡ 1012 (mod m) I am supposed to find all m in the natural system.
0
votes
3answers
68 views

Proof that $(a\cdot a)\bmod b=\Big((a\bmod b)\cdot(a\bmod b)\Big)\bmod b$

I'm trying to prove this kinda of trivial modular attribute, but keep failing. $$(a\cdot a)\bmod b=\Big((a\bmod b)\cdot(a\bmod b)\Big)\bmod b$$ Any ideas?
2
votes
1answer
41 views

Determine $m$ such that $\psi_m:\overline{x}\in\mathbb Z_{16} \to \overline{m}\overline{x} \in \mathbb Z_{16}$ is a bijection etc

Determine $m \in \mathbb Z$ such that $\psi_m:\overline{x}\in\mathbb Z_{16} \to \overline{m}\overline{x} \in \mathbb Z_{16}$ is a bijection. Let $T$ be the set of such $m$ elements, if $m \in T$ is it ...
1
vote
4answers
106 views

Factoring a large integer where the factors are prime

Suppose I know the value of $n$ (where $n = pq$), and I also know $k = p-q$. How can I efficiently factor $n$? Note that I don't know $p$ or $q$. EDIT: Thank you for your answers. I understand that ...
2
votes
2answers
49 views

If $n \geq 1$ is not prime and $x \in\mathbb{Z}_n$ such that $\gcd(x, n) \neq 1$, prove that $x^{n-1} \bmod n \not\equiv 1$.

If $n \geq 1$ is not prime and $x \in\mathbb{Z}_n$ such that $\gcd(x, n) \neq 1$, prove that $x^{n-1} \bmod n \not\equiv 1$. I am not sure why this would be true. So, letting $n$ be a nonprime ...
2
votes
0answers
29 views

Name for summation that returns GCD(k,n)

Define $$ H(k,n)=2\sum_{i=1}^{n-1}\left\lfloor\frac{ki}{n}\right\rfloor\;. $$ We can prove that $H(k,n)=nk-k-n+\gcd(k,n)$. Does this $H$ carry some known name?
1
vote
1answer
87 views

Why just 4 square roots given ($x^2 \bmod N$)

Oblivious transfer algorithm's page on Wikipedia claims: The receiver picks a random $x$ modulo $N$ and sends $x^2 \bmod N$ to the sender Note that $\gcd(x,N)=1$ with overwhelming probability, ...
0
votes
0answers
45 views

Minimum of a linear congruence sub-sequence

I have the following little problem : let $a,b,u,v$ be four given integers with $\gcd(a,b)=1$. Now I would like to find the minimum of the linear congruence subsequence $\{ax \pmod b : u \le x \le ...
3
votes
4answers
107 views

How to solve $ 227x \equiv 1 ~ (\text{mod} ~ 2011) $?

How to solve $ 227x \equiv 1 ~ (\text{mod} ~ 2011) $? I just asked this question, and it seems those methods are not really suitable for large numbers. Please give me some ideas. Thank you.