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
2answers
249 views

Finding modulus by composite number

Let $p_1$ and $p_2$ are prime numbers, $a,b <p_1p_2$. I need to find $ab \pmod{p_1p_2}$. But for some reason I cant find $ab$, it will be too large number. How can I find it without calculating ...
1
vote
2answers
127 views

Prove: $f(x)^{p^k}\equiv f\left(x^{p^k}\right)\bmod p$

$p$ is a prime number, $k$ is an positive integer, and $f\in\Bbb Z[x]$. Prove: $f(x)^{p^k}\equiv f\left(x^{p^k}\right)\bmod p$
4
votes
1answer
328 views

Let $p$ be a prime and $q$ a prime divisor of $2^{p} -1$. Use Fermat's Little Theorem to prove that $q\equiv 1 (\mod \space p)$

Question continued: Hint: Consider $ord_{q}(2)$. Similarly, prove that if $r$ is a prime factor of $2^{2^{k}}+ 1 $ then $r\equiv1 (\mod \space 2^{k+1})$ I think I have the first part, however I ...
0
votes
1answer
33 views

Modular arithmetic on $ 2x^3 - 7y^3 = 3 $

Find integers x and y such that $2x^3-7y^3=3$ How to do it? My first thought was to reduce it to one variable problem by taking suitable mod. 1) mod 7 $ 2x^3\equiv 3 \bmod 7 $ 2) mod 2 $ ...
0
votes
1answer
491 views

Matrix Multiplication under a Modulo

Let $a$ and $b$ be different non-singular square matrices (same dimenstions) where all values are between 0 - 15 Let $c$ = $a.b$ mod 16 (all values in matrix are changed to mod 16) Will ...
2
votes
2answers
217 views

Show that $2^a + 1 $ is divisible by 3 if a is odd.

I understand that this question has been asked before, but I was wondering if I could get clarification in understanding the accepted answer by @Hagen von Eitzen. (Sorry no plagiarism here is ...
1
vote
0answers
29 views

Reasoning about $\left\lfloor\frac{p_k\#}{p_{k+1}}\right\rfloor$

This is a follow up question to my previous question. Let $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} ...
1
vote
1answer
25 views

Trying to understand why a set of residues modulo a primorial $p_k\#$ has a range of values smaller than $2p_{k+1}$

I've been reviewing the following: $$v_i = \left\lfloor\frac{ip_k\#}{p_{k+1}}\right\rfloor + c_i$$ where: $c_i \in \left\{1,2\right\}$ so that $v_i$ is odd and $v_ip_{k+1} > ip_k\# > ...
1
vote
1answer
32 views

If we know that $A\equiv x\pmod{M}$, can we know what $x\pmod{m}$ is for any other $m$?

Given two integers $A$ and $M$ such that $A = x \pmod {M}$ where $x$ is an unknown integer. Is it possible to find out the answer for $x \pmod {m}$ where $m$ is any other given number ?
0
votes
0answers
50 views

How to compute the number of solutions of primitive modulo equation?

Consider the equation: $$x^p \equiv a \pmod{M}$$ where $p, a$ and $M$ is given. Is there a quick way to compute the number of solutions to the above equation? I'm so rusty in Number Theory now, so ...
2
votes
0answers
59 views

How to find connection between two modulo statements

Given $x\mod n=a$ and $ x\mod m=b$, (here, $n=1000000007$ while $m$ can be any number less than $n$) is there any meathod to find $b$ in terms of $(n,a,m)$...The answer should not contain $x$. I tried ...
1
vote
1answer
45 views

Solving modular equations for solutions.

Given $k, p, q$, we need to find the solutions for $x ^{k}\equiv p$ (mod $q)$. How to find the number of solutions for $x$ up to some upper limit of $x$.
1
vote
2answers
183 views

what is the remainder when $(17^{3}+19^{3} + 21^{3}+23^{3})$ is divided by 83?

what is the remainder when $(17^{3}+19^{3} + 21^{3}+23^{3})$ is divided by 83? NOTE:$a^{3}+b^{3}=(a+b)(a^2-ab+b^2)$
1
vote
2answers
158 views

Random math questions (modular arithmetic & notation)

I found this amazing wall clock picture on the internet but I really don't know a few things. I don't know what's $B'_L$, &#x33;, why $2^{-1}\equiv 4[7]$ and ...
2
votes
1answer
396 views

How to find a mod m when modulus of a mod powers of 2 are given

I need to find the value of a mod m. But I don't have the value of a directly. I have the following modulus values of ...
1
vote
1answer
293 views

Solutions of non-linear congruence equation

I am trying to find the number of solution to $$ x^a(\mod b) =c:0\leq x\leq l$$ where $b\leq50$ but $a$ and $l$ can be large. My approach is to iterate through each value of $x$ from $0$ till ...
2
votes
1answer
34 views

How to compute $a \pmod{m_1}$ given that $a \equiv c \pmod{m_2}$?

Given $m_1, m_2$ and we know that $$a \equiv c \pmod{m_1}$$ Is there a way to directly compute $$a \pmod{m_2}$$
1
vote
0answers
197 views

Modular arithematic Equation

We have an equation: $a^x+b^x+c^x \equiv m \pmod n $ also given $a,b,c < y $ what are the total number of solutions of this equation?
1
vote
1answer
68 views

$abc$ mod $m$ vs division

Consider four positive integers $a,b,c,m$ and the modular product $bc = x$ mod $m$. Theoretically should I not be able to find $x$ by doing $abc / a$ mod $m$? I am not sure how this is done since ...
1
vote
1answer
70 views

Modulus between different fields

If I have a value: A mod P, where P is a prime number, and A=a*b*c*d.... n elements. Is there a way to transform this product modulo some other number which is co-prime to P. Like A mod M. Or will ...
3
votes
4answers
971 views

find a solution of 9x = 24 (mod 21)

I need help finding a solution of $9x\equiv {24}\pmod {21}$. Here is what I tried, but it's wrong. mod x is the positive value of x. mod $21 = 21.$ $9x\equiv {24}\pmod {21}$. $9x = 24*21$ $x = ...
1
vote
0answers
51 views

Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
3
votes
0answers
87 views

Equivalence classes of triplets satisfying $x^2+y^2+z^2=0$ over $\mathbb{F}_p$

The affirmative answer to this question illustrates that the equation $$x^2+y^2+z^2=0$$ has $p^2-1$ nontrivial solutions over $\mathbb{F}_p$ (solutions that are not $(0,0,0)$). If $(x,y,z)$ is a ...
5
votes
4answers
150 views

Polynomial modulus

Can anyone explain why the two solutions to $n^2+7n-2 = 0$ modulo $43$ are $n=13$ and $n=23$ and how they are found?
0
votes
2answers
70 views

Explain why it is true that if $7^{30}$, $7^{20}$ and $7^{12}$ are not congruent to 1 mod 61, then 7 is a primitive root mod 61

Notice that $60 = 2^2 \cdot 3 \cdot 5$. Explain why it is true that if $7^{30}$, $7^{20}$ and $7^{12}$ are not congruent to $1 \mod 61$, then $7$ is a primitive root $\mod 61$. Here is what I ...
1
vote
3answers
76 views

What is modular arithmetic?

I always see questions on here that deal with this modular stuff, and I have no idea what any of it means, so I figured I would ask here. So lets say we have $$a \equiv b\pmod n$$ The example on ...
1
vote
1answer
46 views

How is the following relation involving modulo operation equal?

Why does the following equation hold? $$\frac{2^{lk}-1}{2^l-1}\bmod p=(2^{lk}-1)(2^l-1)^{p-2} \bmod p,$$ where $p=100000007$ That is (in more standard mathematical notation), ...
1
vote
1answer
22 views

generating a vector given other vectors in modulo 11

how to show that vector $X4=\begin{bmatrix}0 \\ 2 \\ 1 \\ 1\end{bmatrix}$ can be generated with $X1=\begin{bmatrix}9 & 1 & 0 & 0\end{bmatrix}$ $X2=\begin{bmatrix}8 & 0 & 1 & ...
1
vote
1answer
92 views

how to interpret theorem about polynomial factorization over modulo ring?

polynomial $X^n+a_1X^{n-1}+...+a_n \in \Bbb Z_2[X]$ doesn't have linear factors $\iff a_n(1+\sum a_i) \neq 0$. How then $f(X)=X+1$ can has no linear factors? Doesn't the condition expands to ...
5
votes
3answers
86 views

Evaluate $\sum\limits_{(m,n) \in D,m < n} \frac{1}{n^2 m^2} $ where $\gcd(m,n)=1$

i have no clue on how to evaluate: $$\sum\limits_{(m,n) \in D,m < n} \frac{1}{n^2 m^2} \text{ where }D = \{ (m,n) \in (\mathbb{N}^*)^2 \mid \gcd(m,n) = 1\} $$ If someone is able to give me a ...
5
votes
1answer
48 views

$p\nmid 2n-1,$ then $\sum_{k=1}^{p-1}\frac{1}{k^{2n-1}}\equiv 0 \pmod{p^3} \Leftrightarrow \sum_{k=1}^{p-1}\frac{1}{k^{2n}}\equiv 0 \pmod{p^2} $

Is it true that if $p$ is a prime and $p\nmid 2n-1,$ then $$\sum_{k=1}^{p-1}\frac{1}{k^{2n-1}}\equiv 0 \pmod{p^3} \hspace{12pt}\Leftrightarrow \hspace{12pt} \sum_{k=1}^{p-1}\frac{1}{k^{2n}}\equiv ...
1
vote
1answer
64 views

using Gauss' algorithm (for linear congruences) for A > B

To solve $Bx \equiv A \pmod{m}$, use Gauss' algorithm. The algorithm works perfectly when $A < B$. For example, to solve $6x \equiv 5 \pmod{11}$: $$x \equiv \frac{5}{6} \equiv \frac{5(2)}{6(2)} ...
3
votes
1answer
631 views

Finding multiplicative inverse modulo n using matrix method

According to this video (15:17 onwards), there is a "matrix method" to find the multiplicative inverse of $a$ mod $n$ by row reducing $$\begin{bmatrix} a & 1\\ n & 0 \end{bmatrix}$$ In the ...
5
votes
0answers
79 views

Constructing pairs of units $(x,y)$ which solve $x^2 + y^2 \equiv -1 \pmod{N}$

A classic result on the way to the Lagrange Four Squares theorem — for instance proven by Theorem 87 of Hardy & Wright, as noted by this remark on the Four Squares theorem — is that ...
1
vote
6answers
111 views

Is it possible to calculate $3^{-1}\equiv ?\pmod{10}$?

If I wanted to calculate $3^{-1}\equiv ?\pmod{10}$ would I first calcuate $3^1$ which is just $3\equiv 3\pmod{10}$ and then divide both sides by $3^2$ which would get $3^{-1}\equiv 3^{-1} mod{10}$ ...
0
votes
0answers
29 views

Help Understanding Provided Solution

I struggled with this problem for awhile before finally giving in and looking at the solution: "Let $n > 1$ be an integer, $A = \mathbb{Z}/n$ the integers modulo $n$ and $G$ the set of maps $\tau ...
2
votes
1answer
61 views

Find solutions to $(v-u)(v+u-1) \equiv 0 ~ (\text{mod }2(v-1))$

How do we find solutions $(u,v)$ to the congruence $$(v-u)(v+u-1) \equiv 0 ~ (\text{mod }2(v-1))$$? Specifically, we would like to find all solutions with $v$ and $u$ positive integers and $v \geq ...
3
votes
1answer
160 views

How do you solve an algebraic equation over a ring?

I have the following equation: $$n^2-n+1=0$$ Where $n$ is an element of a ring over elements $\{-2,-1,0,1,2\}$, and addition and multiplication are defined modularly (e.g. $2+1=-2$). How would you go ...
2
votes
1answer
132 views

Quadratic congruences

Is there an algorithm to solve the quadratic congruence $x^2\equiv D \pmod m$ for any $D$ and $m$? I searched a bit and found algorithms for $m$ prime and $\gcd(D, m) = 1$. None of them gave a ...
1
vote
1answer
60 views

difference between angles

i could not understand exactly what is asked in the following question: What is difference in the degree measures of the angles formed by Hour hand and minute Hand of a clock at $12:35$ and ...
0
votes
1answer
53 views

Is this possible to find modulo of different value and get same result?

Is it possible, for $a,b,m,n,x,y\in\mathbb N$ to have $$x = y^a \pmod n \qquad \text{ and }\qquad y = x^b \pmod m ?$$ For example: $17=5^{11} \pmod{21}$ and $5=17^{11} \pmod{21}$ is an integer but ...
1
vote
7answers
209 views

What does $a\equiv b\pmod n$ mean?

What does the $\equiv$ and $b\pmod n$ mean? for example, what does the following equation mean? $5x \equiv 7\pmod {24}$? Tomorrow I have a final exam so I really have to know what is it.
4
votes
1answer
247 views

How to find the smallest positive integer $K$ such that $(K -\lfloor\frac{K}{2}\rfloor + 1)(\lfloor\frac{K}{2}\rfloor + 1) \geq N$

I am writing a program and I would need an explicit formula for the following: The smallest positive integer $K$ such that: $$\left(K - \left\lfloor\frac{K}{2}\right\rfloor + ...
4
votes
2answers
81 views

If $m \equiv n \pmod{A}$, then $s^m \equiv s^n \pmod{A}$?

I'm kind of stuck with the following assignment: Prove: If $m \equiv n \pmod{A}$, then $s^m \equiv s^n \pmod{A}$ I tried $m = k_1 \times A + r$ , and $n = k_2 \times A + r$ , then $s^m = s^{k_1 ...
0
votes
1answer
350 views

Calculating $1819^{13} \pmod{2537}$ using Fermat's little theorem

Can anyone make me understand how to calculate $1819^{13} \pmod{2537}$ using Fermat's little theorem? Here $p=2537$ and $p-1=2537-1=2536$. I am unable to understand how to express $1819^{13}$ in ...
1
vote
0answers
53 views

Specific Modular Arithmetic Question with Exponentiation

Are there any theorems that can be used to reduce $1213^{797} \pmod {2591}$ without using a computer?
1
vote
4answers
368 views

Can modulo be used in consecutive multiplications or divisions?

I used to participate in programming competitions and at times I see that the solution should be the remainder when divided with some big prime number (usually that would be 1000000007). In one of the ...
3
votes
0answers
81 views

An intuitive interpretation of Montgomery pair corrlation function vs. prime divisibility?

Theorem - If the Riemann hypothesis would be true, and the Montgomery pair correlation conjecture (see linked article page 183-184) true too; let $p \in \Bbb P$ prime, $n \in \Bbb N$ and $$\mathcal ...
3
votes
1answer
79 views

Stumped by a notation.

I'm reading through http://cr.yp.to/papers/primesieves.pdf and came across the following notation on p. 1: For example, a squarefree positive integer $p \in 1 + 4\Bbb Z$ is prime if and only if ...
5
votes
1answer
62 views

Why does $6^x ≡ 2^{10-x} \pmod{11}$ when $0≤x≤10$?

I was messing around with my calculator earlier today. I graphed the function $6^x \pmod{11}$, and I noticed a pattern, and I "discovered" the following: $$6^x ≡ 2^{10-x} \pmod{11}$$ This works ...