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
4answers
59 views

Congruence relation possible typo?

Is the following a typo? If $a \equiv b \pmod{m}$, then for some scalar $c>0$, $ac \equiv bc \pmod{mc}$ Or should it be $\pmod{m}$?
2
votes
1answer
80 views

simple congruence with large power and large moduli

I am trying to compute $2^{111455} \pmod{2012}$, but since the numbers are too large, I don't know how to compute it efficiently. I've got: $2012=2^2 \times 503$, $503$ is a prime. And that ...
0
votes
1answer
55 views

how to work out $14^{293}-12^{26}\pmod{13}$

How can I work this out without a calculator? $$14^{293}-12^{26} \pmod{13}$$ I just couldn't figure out a way to do this.
4
votes
2answers
236 views

Solving Pell's equation(or any other diophantine equation) through modular arithmetic.

Let us take a solution of Pell's equation ($x^2 - my^2 = 1$) and take any prime $p$. Then we have found a solution of the Pell's equation mod $p$. Now, conversely, for any prime $p$, we can find a ...
2
votes
1answer
147 views

How to compute the remainder of a division $a/b$ to a modulus $M$, i.e. $a/b \pmod M$

I am learning the usage of mod in programming to overcome the overflows. I was able to deduce the following relation ships: for example if I want to perform addition between $a$ and $b$ and the ...
1
vote
4answers
61 views

Modular arithmetic: How to solve $3^{n+1} \equiv 1 \pmod{11}$?

Please, I can't solve this equation: $$3^{n+1}\equiv 1 \pmod{11}$$ for $n \in \mathbb{N}$. So what should I do please? Thanks.
0
votes
2answers
48 views

Looking for an integer for which the $(\mathbb{Z}/n\mathbb{Z})^*$ contains elements with certain orders

I don't need a specific answer or whatever, but I'm looking for a strategy to solve this kind of problems. The specific question I have in mind is: Give an integer $n$ for which the multiplicative ...
1
vote
1answer
247 views

Homomorphism between multiplicative group of integers modulo n

Just looking for anybody to check the following: We have got a homomorphism $f: (\mathbb{Z}/42\mathbb{Z})^{*} \rightarrow (\mathbb{Z}/21\mathbb{Z})^{*}$, given by $f(a\text{ mod} 42)= a \text{ mod} ...
4
votes
3answers
2k views

Using Fermat's Little Theorem, find the least positive residue of $3^{999999999}\mod 7$

I'm going through the problems in Rosen's Elementary Number Theory and am having some trouble with the this problem, Find the least positive residue of $3^{999999999}\mod 7$.
2
votes
3answers
123 views

Why is it that, $\forall x \in \mathbb{Z},\ x^5 \equiv x \pmod{10}$? [duplicate]

Just playing around, I realized that $x^{5}\equiv x \pmod{10}$ for all integral $x$. Euler's theorem explains this for $x$ coprime with $10$, as for such $x$, $x^{4}\equiv 1$, but I don't know why ...
1
vote
2answers
33 views

What is $\operatorname{max}(x)$ given that $ x \equiv n^p \pmod{q}$?

Look at this: $$ x \equiv n^p \pmod{q} $$ What is $\operatorname{max}(x)$?
1
vote
1answer
166 views

Homework problem on identifying a sequence

I had this problem in my discrete math/modular arithmatic course where I had to find the first 10 terms of a series F(r), starting from F(3). The given information is: F(3)=1 F(4)=13 F(10) % ...
5
votes
1answer
157 views

A simpler proof that if $m\mid n$ then there is a ring homomorphism from $\mathbb{Z}_n$ onto $\mathbb{Z}_m$?

Question 18.I.4 from Pinter's A Book of Abstract Algebra asks for a proof of the following, where $\mathbb{Z}_m$ and $\mathbb{Z}_n$ are treated as rings: If $n$ is a multiple of $m$, then ...
2
votes
2answers
48 views

Does $((x-1)! \bmod x) - (x-1) \equiv 0\implies \text{isPrime}(x)$

Does $$((x-1)! \bmod x) - (x-1) = 0$$ imply that $x$ is prime?
3
votes
3answers
122 views

Remainder of $8\times 8\times 8\times 8\times 8\times 8$

What is the remainder of $8\times 8\times 8\times 8\times 8\times 8$ divided by $7$ ? It is related to modulo calculus. Can somebody give me the hints to solve it ?
4
votes
2answers
257 views

Telephone Number Checksum Problem

I am having difficulty solving this problem. Could someone please help me? Thanks "The telephone numbers in town run from 00000 to 99999; a common error in dialling on a standard keypad is to punch ...
3
votes
0answers
2k views

Curious 123456789 x 8 + 9 = 987654321

I was recently asked why the following results holds \begin{align} 1 \times 8 + 1 &= 9 \\ 12 \times 8 + 2 & = 98 \\ 123 \times 8 + 3 & = 987 \\ 1234 \times 8 + 4 & = 9876 \\ 12345 ...
1
vote
2answers
57 views

Is there some nomenclature to get the remainder of a value?

I want to write a formula where I can say that I have to get the remainder of a division by 4. $y = \mathbf{remainder}(x\div4)$ Is there any math nomenclature I can use?
0
votes
1answer
54 views

Distribution of Modular Expressions

This is really a programming question that I'm unable to solve because of a math question. I'm having a problem understanding the rules of distribution with modular arithmetic. I have two ...
2
votes
2answers
681 views

Equation Calculating what Day it is

Consider this word problem: If the first day of the year is a Monday, what is the 260th day? Answer: Monday Why does this equation work to calculate what day of the week it is: 260 = (7w + 1) [w ...
3
votes
1answer
218 views

Solve a system of linear congruences

I have this system: $$ \begin{align} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n &= b_1 \mod p \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n &= b_2 \mod p \\ \vdots \\ ...
1
vote
0answers
55 views

How can I solve this using BIT?

I found a nice math problem, but I still can't solve it, I tried to find one solution using google and found that it can be solve using the Binary Indexed Tree data structure, but the solution is not ...
3
votes
1answer
121 views

Is the number of quadratic nonresidues modulo $p^2$, greater than the number of quadratic residues modulo $p^2$?

Let $p$ be a prime. The number of quadratic nonresidues modulo $p^2$, is greater than the number of quadratic residues modulo $p^2$. Is that statement true or false? Why? Thank you.
5
votes
4answers
3k views

Solve Modular Equation $5x \equiv 6 \bmod 4$

Here is an modular equation $$5x \equiv 6 \bmod 4$$ And I can solve it, $x = 2$. But what if each side of the above equation times 8, which looks like this $$40x \equiv 48 \bmod 4$$ Apparently ...
-1
votes
2answers
98 views

Congruent Modulo with negative

16 = 7 (mod m) Find m: 7-16 = -9 so the m can be what ever can divide into -9 ?
0
votes
2answers
50 views

Determine amount of congruent numbers

I found the claim in a paper that there are at max 8 integers mod $2^{130}-5$ congruent to one integer mod $2^{128}$. $$u \pmod {2^{130}-5} \equiv g \pmod {2^{128}} \quad\text{ with }u \in U \quad ...
0
votes
3answers
63 views

MODULAR problem

What will be the remainder when 64! is divided by 71? Do we need to solve this problem by using MOD theorem or need to expands the factorial?
2
votes
2answers
55 views

Modular Arithmetic & Congruences

Show that if $p$ is an odd prime and $a \in \mathbb Z$ such that $p$ doesn't divide $a$ then $x^2\equiv a(mod p)$ has no solutions or exactly 2 incongruent solutions. The only theorem that I ...
3
votes
2answers
43 views

How can I answer this question? (Modular)

-3 $\equiv$ 17 Find the mod number: Ex: -3 $\equiv$ 17 (mod 5) How would I find the mod number ?
0
votes
1answer
46 views

Square modulus question

"If $p ≡ 1 \pmod 4$ or $q ≡ 1 \pmod 4$, $p$ is a square $\pmod q$ iff $q$ is a square $\pmod p.$ What does "square mod q" means? I can't understand this statement.
1
vote
6answers
237 views

Solving a Linear Congruence

I've been trying to solve the following linear congruence with not much success: 19 congruent to $19\equiv 21x\text{ (mod }26)$ If anyone could point me to the solution i'd be grateful, thanks in ...
3
votes
5answers
136 views

For any integer $a$, there is an integer $k$ such that $a^2=3k$ or $a^2=3k+1$

Let $a$ be an integer. Prove that there exists an integer $k$ such that $a^2=3k$ or $a^2=3k+1$. Here is what I did: I said: $a\in\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$. When I put 2 into $a^2$, I ...
2
votes
2answers
96 views

Has anyone studied this operator?

I've been studying a particular unary operator on the commutative ring $\mathbb{Z}/n\mathbb{Z}$. The operator is: $\downarrow(x) = y\pmod{n}$ iff $n \equiv y \pmod{x}$, where $0< x,y \le n$. The ...
1
vote
5answers
100 views

Showing that $a^{12}\equiv 1\pmod{210}$ if $a$ is coprime to $210$

I ran into this next question: Show that if $a$ is coprime to $210$: $a^{12}\equiv1 \pmod{210}$. This is not a homework question. Thank you very much in advance, Yaron
3
votes
2answers
108 views

What is 8 times 9 in 12-hour clock arithmetic?

What is $8\times 9$ in $12$ hour arithmetic? Will it be $0$, or will it be $6$? $8*9 = 72$ and $72/12 = 6$ So is the answer $0$ or $6$?
0
votes
2answers
55 views

Evaluating the congruence $(1+195) \pmod 7$

$$(1 + 195) \pmod 7 \equiv \quad ?$$ How would I get the answer? Because when I divide $196 / 7$ I get $28$ which is not a decimal to multiply by $7$.
1
vote
3answers
148 views

addition with a variable (mod)

(2+x) = 7 (mod 3) 2 + 0 = 2 2 + 1 = 3 2 + 2 = 4 . . 2 + 5 = 7 <-- so the answer will be x = { 5, 8, 11, 14, 17 .. } Is this correct? Because somebody told me the answer should be x = { 2, 5, ...
1
vote
4answers
92 views

Modulo question about equality

True or false? $$24 \equiv 77 \mod 16 $$ $1.$ $77/16 = 4.8125 $ $2.$ $4.8125 - 4 = .8125$ $3.$ $0.8125 \times 16 = 13$ $4.$ $24 != 13$ So the answer is false? Am I right?
2
votes
3answers
77 views

If $x\equiv y \pmod{\gcd(a,b)}$, show that there is a unique $z\pmod{\text{lcm}(a,b)}$ with $z\equiv x\pmod a$ and $z\equiv y\pmod b$

If $x\equiv y \pmod{\gcd(a,b)}$, show that there is a unique $z\pmod{\text{lcm}(a,b)}$ with $z\equiv x\pmod{a}$ and $z\equiv y\pmod{b}$ What I have so far: Let $z \equiv ...
2
votes
3answers
150 views

Prove that if $p_1,\dots,p_k$ are distinct odd primes then 1 has $2^k$ square roots $\mod m$ where $m$ is the product of the primes.

I think I am most of the way through this proof but I am stuck. Here was my approach: I looked at the square roots of $1$ mod $105$, and noticed that each one corresponded to one less than an integer ...
1
vote
3answers
45 views

Finding $a \pmod c$ if $a \pmod b$ is known

Suppose that: $Y \pmod B = 0$ $Y \pmod C = X$ I know $B$ and $C$. $Y$ is unknown, it might be an extremely large number, and it does not interest me. The question is: Is it possible to find $X$, ...
1
vote
2answers
63 views

Modulo question with negative

$60-88 \equiv \,\,? \pmod 5$ $60-88 = -28$ Then what do I do? Please tell me how to answer this question. Thanks.
2
votes
2answers
206 views

What is the distribution of primes modulo $n$?

Let $n\geq 2$ and let $k$ be "considerably larger" than $n$ (like some large multiple of $n$). Then for each $i$ such that $0<i<n$ and $\gcd(i,n)=1$ let's define $$c_i=\left|\{p_j\;|\; p_j\equiv ...
1
vote
2answers
72 views

Factorization in Gaussian integers

Let $p$ be a natural number, suppose $p$ prime. Show that the following conditions are equivalent: 1) the polynomial $x^2+1\in\mathbb{Z}_p$ has roots in $\mathbb{Z}_p$ 2) $p$ is reducible in the ...
3
votes
2answers
56 views

Primality test based on initial conditions alone.

Let $m=252601$. Suppose we discover that $$3^{126300} ≡ 67772 \pmod{252601}$$ $$3^{252600} ≡ 1\pmod{252601}$$ Is then $252601$ prime? composite? Or can we not decide for sure from the information ...
2
votes
3answers
220 views

What is the least nonnegative number $a$ congruent to $3^{340}\pmod{341}$?

Find the least nonnegative number $a$ congruent to $3^{340} \pmod{341}$. What steps should I take to get to the answer?
3
votes
2answers
92 views

Two questions on clock arithmetic

I have two questions on clock arithmetic, both of which I have solved, but I am looking for neater proofs. Let us suppose we have a circle named $\mathbb{Z}_n$ with $n$ equally spaced points on it ...
3
votes
1answer
241 views

How many solutions does this equation have $x^2 \equiv 1017 (\mod 2^k)$

How many solutions does this equation have $x^2 \equiv 1017 \ \mod 2^k$? I know that $1017 \equiv 1 \mod 8$? I think that for $k=1$ we have $x^2 \equiv 1017 \mod 2$ and the solution is $x=1 \mod 2$ ...
0
votes
3answers
110 views

$2^{q-1}\equiv 1\pmod{q}.$

The question is asking to show that $q$ must be prime given $$ 2^{q-1}\equiv 1\pmod{q}. $$
1
vote
3answers
112 views

Inverse | Modulo | Power

Describe the inverse of $5$ modulo $18$ as a positive power of $5\pmod{18}$. I've got that the inverse of $5$ is $11$, but is this question asking to find a $t$ such that $$ 11=5^t\pmod{18}?$$