Tagged Questions

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

3
votes
4answers
944 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
148 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
74 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
85 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
62 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
599 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
158 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
131 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 ...
28
votes
1answer
750 views

Is $\sqrt1+\sqrt2+\dots+\sqrt n$ ever an integer?

Related: Can a sum of square roots be an integer? Except for the obvious cases $n=0,1$, are there any values of $n$ such that $\sum_{k=1}^n\sqrt k$ is an integer? How does one even approach such ...
1
vote
1answer
59 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
238 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
79 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
331 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
52 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
357 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
79 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
78 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
58 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 ...
-1
votes
1answer
72 views

Conjecture on limit of $1-(n^{p-1}\mod p)$

Given $p \in \Bbb P$ prime, $n \in \Bbb N$ and $$\mathcal V_p=1-(n^{p-1}\mod p)$$ let me conjecture that $$\lim_{p\rightarrow \infty}\mathcal V_p = \operatorname{sinc}(2\pi \,n)$$ Question: Is ...
1
vote
1answer
138 views

Remainder problem using MOD

What's the remainder when $ 43^{101} + 23^{101}$ is divided by 66? If we use the remainder obtained when $ 43^{101} + 23^{101}$ is divided by $66$, then it becomes, $$13^{101}+23^{101}$$ then how ...
4
votes
2answers
116 views

Diophantine equation $x^2-dy^2=k$ in $\mathbb{Z}_n$

Does anyone know when $x^2-dy^2=k$ is resoluble in $\mathbb{Z}_n$ with $(n,k)=1$ and $(n,d)=1$ ? I'm interested in the case $n=p^t$
4
votes
1answer
153 views

Length of recurrent strings of numbers in the decimal expansion of $1/p$, where $p$ is prime.

Am I right to assume that: all rational numbers have a recurrent sequence in their decimal expansion, and the length of the expansion of $1/p$, where $p$ is prime, is $p-1$ for sufficiently large ...
1
vote
1answer
151 views

how to solve $ax+by=c \mod p$?

Given $a$, $b$, $c$ (integers), and $p$ (prime), Is there any general solution for $ax+by=c \mod p$? I found that it has similar form to solving $ax=c \mod p$, but cannot find the connection between ...
0
votes
1answer
31 views

Can I prove bounds on this modular equation…

Hypothesis: $\forall$ odd $n > 1$, $\exists\ m <n$ such that $2^m = 1\mod n$. This seems to hold for small values. For example: For $n=5$, $m=4$ satisfies as $2^4 = 16 = 1\mod5$. For $n=65$, ...
-1
votes
1answer
53 views

Question about modular arithmetic proofs

I'm having trouble with the following proof: For any integer x and any integer k, x (mod k) = x. Can anyone help with this?
1
vote
3answers
105 views

Find $n$ such that $x^n \equiv 2 \pmod{13}$ has a solution

I am stuck on the following problem: Consider the congruence $x^n\equiv 2\pmod{13}$. This congruence has a solution for $x$ if $n=5$ $n=6$ $n=7$ $n=8$ Can someone explain in ...
2
votes
1answer
164 views

If the dividend is multiplied by a given number, and divided by the same divisor, the new remainder is multiplied by the same number?

In a division, if the (the number which is being divided) is multiplied by certain factor and then divided by the same divisor, then the new remainder will be obtained by multiplying the original ...
4
votes
2answers
104 views

Valid Alternative Proof to an Elementary Number Theory question in congruences?

So, I've recently started teaching myself elementary number theory (since it does not require any specific mathematical background and it seems like a good way to keep my brain in shape until my ...
1
vote
0answers
64 views

Why does this imply these two numbers are the same mod 8?

I was looking over the solution to a problem here (http://www.artofproblemsolving.com/Wiki/index.php/2013_AMC_12B_Problems/Problem_14). What has me confused, is where they say that $5x_{1} + 8x_2 = ...
0
votes
2answers
186 views

Show that there is no complete set of representatives for $\mathbb Z/71\mathbb Z$ that includes two of the numbers 1066, 1492, and 1776.

Show that there is no complete set of representatives for $\mathbb Z/71\mathbb Z$ that includes two of the numbers $1066, 1492$, and $1776$. My plan is to add the first two representatives of the set ...
1
vote
2answers
196 views

Which of the following sets is a complete set of representatives modulo 7?

Which of the following sets is a complete set of representatives modulo 7? 1) (1, 8, 27, 64, 125, 216, 343) 1 mod 7 = 1 8 mod 7 = 1 27 mod 7 = 6 64 mod 7 = 1 125 mod 7 = 6 216 mod = 6 343 mod ...
2
votes
2answers
156 views

Math Parlor Trick

A magician asks a person in the audience to think of a number $\overline {abc}$. He then asks them to sum up $\overline{acb}, \overline{bac}, \overline{bca}, \overline{cab}, \overline{cba}$ and ...
7
votes
4answers
976 views

Calculating 7^7^7^7^7^7^7 mod 100

What is $$\large 7^{7^{7^{7^{7^{7^7}}}}} \pmod{100}$$ I'm not much of a number theorist and I saw this mentioned on the internet somewhere. Should be doable by hand.
2
votes
4answers
600 views

If $w^2 + x^2 + y^2 = z^2$, then $z$ is even if and only if $w$, $x$, and $y$ are even

I'm trying to go through the MIT opencourseware Mathematics for Computer Science (6.042J). I've been stumped for half a day trying to figure it out. Something isn't clicking, and I could use some ...
2
votes
1answer
205 views

Application of the Chinese Remainder Theorem

Three brothers A, B and C live together and they all love eating pizza. A has the habit of eating a pizza every 5 days, B every 7 days and C every 11 days. A and C both eat pizzas together on 3 ...
1
vote
1answer
362 views

Encryption using modular addition and a key

Problem i'm facing says: The value representing each row is encrypted using modular addition with a modulus of 32 and a key of 27. I sort of figured out what ...
0
votes
2answers
56 views

Explanation of $\equiv$, and which of these statements involving it are true?

I am not familiar with this three lines equal sign and reading about it didnt really help with the original problem, which is: From the options below choose up to two that show correct solutions ...