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
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
98 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
91 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
2answers
82 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
829 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
81 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
115 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
31 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
181 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
142 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
72 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
286 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
84 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
454 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
465 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
87 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
80 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 ...
-1
votes
1answer
73 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
157 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
120 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
182 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
194 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
57 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
110 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
201 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
113 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
69 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
205 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
255 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
173 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 ...
8
votes
3answers
1k 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
813 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
332 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
469 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 ...
2
votes
2answers
85 views

Large exponential modular

Proof $2011^{2011^{2011}}-2011 \equiv 0 \mod 30030$ By Chinese Remainder Theorem this is equivalent to proving: $2011^{2011^{2011}}-2011 \equiv 0 \mod 2$ $2011^{2011^{2011}}-2011 \equiv 0 \mod 3$ ...
5
votes
2answers
397 views

On the number of quadratic residues $\pmod{pq}$ where$p$ and $q$ are odd primes.

I have read that the formula for the number of quadratic residues $\pmod{pq}$ for odd primes $p$ and $q$ is $\frac{(p-1)(q-1)}{4}$. Is this the case, and if it is, why is it the case and how would one ...
2
votes
1answer
76 views

Why inverse modulo exponentiation is harder than inverse exponentiation without modulo

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. ...
3
votes
4answers
254 views

What is $2012^{2011}$ modulo $14$?

$$2012^{2011} \equiv x \pmod {14}$$ I need to calculate that, all the examples I've found on the net are a bit different. Thanks in advance!
4
votes
1answer
69 views

Symmetry in reduced residue systems

This may be a stupid question, but it looks to me like the reduced residue systems modulo N are symmetrical about N/2; that is to say, that the there is the same number of integers not divisible by a ...
2
votes
0answers
35 views

Least value of a multi-residue CRT

Given coprime moduli $m_1,\ldots,m_n$ with $k\ge2$ residues in each modulus, what is the least nonnegative value congruent to one of the specified residues to each modulus? Obviously it must be less ...
2
votes
3answers
228 views

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$?

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$? Here's what I've done: $1^3$ congruent to $1 \pmod p$ thus, 1 is a cubic residue, ...
2
votes
1answer
368 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...