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
0answers
29 views

Strategies to find the commonality of a set of prime numbers

I have a set $E$ of prime numbers that are the error results of a test. I would like to isolate them at least partially, so I am trying to find a non basic commonality between them. UPDATE: As ...
3
votes
1answer
20 views

How to tell if a set of simultaneous congruences is solvable?

Let's say we have a set of N simultaneous congruences that looks like this: x ≡ c1 (mod m1) x ≡ c2 (mod m2) ... x ≡ cN (mod mN) Currently, to check if this set has a solution I have to go ...
5
votes
3answers
108 views

Modulos race, which formula reach 100 first?

I would like to know if there was a way to determine according to this formula: \begin{equation*} \sum_{i=0} \frac{A*i+B \pmod{100}}{100} \end{equation*} and the same with different values of A and B ...
3
votes
4answers
63 views

Is this a valid way of solving modular equations?

Some of the exercises in my abstract algebra textbook involve solving congruence equations, for example $$5x \equiv 1 \pmod 6$$ I convert that to a linear equation by rewriting $$x = \frac{k6+1}{5} = ...
3
votes
2answers
70 views

what is remainder when $(((3!)^{5!})^{7!})^{9!…}$ is divided by 11

$$(((3!)^{5!})^{7!})^{9!...}$$ when divided by 11 what will be the reminder? Hint is appreciated Sorry I do not know how to start this problem, so I have not shown my efforts!
2
votes
1answer
19 views

Sequences formed by integer evaluations of polynomials modulo $ p^{k} $, where $ p $ is a prime number and $ k \in \Bbb{N} $.

I have the following question. Let $ p $ be a prime number and $ k $ a positive integer. Let $ (a_{n})_{n \in \Bbb{Z}} $ be a two-way sequence in $ \Bbb{Z} / p^{k} \Bbb{Z} $. Then is it true that ...
1
vote
1answer
50 views

Solvability of the congruence $(x+a)^n\equiv x^n\pmod p$ in $x$

When thinking about solving the diophantine $x^n-y^n=1001$ I noticed that my knowledge about the prime factorisation of $x^n-y^n$ does not suffice to attack such diophantines in general. Note I'm ...
0
votes
0answers
21 views

Factorization of a number obtained by a modular multiplication operation can reveal factors of the used operands?

Consider a number $r$ obtained by: $r=a⋅b \mod n$ Knowning the factorization of $r$ can reveal some information (bits) of $a$ and $b$ ?
0
votes
1answer
45 views

Prove, if $n>6$ is an even, perfect number, then $n\equiv4 \pmod 6$

I've been working on this for quite awhile, and am stumped after a little bit. I have some stuff written down, but I just don't know how to completely prove it. I don't have much done yet: ...
1
vote
1answer
54 views

how to solve $3x^3\equiv 7\pmod{925}$

I am trying to solve $3x^3\equiv 7\pmod{925}$ I thought using Brute Force but $925$ is too big for that. Also i tried raising both sides of the equation to power of $3$ but it didn't help. How can ...
0
votes
0answers
35 views

Modular arithmetic, specifically n! mod m

Is there a theorem that makes solving $$ n! \equiv x \mod m $$ knowing that both $n$ and $m$ are prime? And if not, what would be the best way to go about finding $x$? cheers
2
votes
4answers
91 views

Prove that $a$ and $a^{-1}$ inverse have the same order in $Z_n$

So there is a question in my lecture notes that I'm not too sure how to approach. It reads as follows: Suppose $a$ is invertible modulo $n$. Prove that $a$ and $a^{-1}$ have the same order in ...
104
votes
1answer
6k views

A variation of Fermat's little theorem

Fermat's little theorem states that for $n$ prime, $$ a^n \equiv a \pmod{n}. $$ The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence ...
2
votes
1answer
25 views

Distributive modulo?

I would like to know if the modulo operation has distributivity like this: $$A+B+C \pmod{M} = (A+B)\pmod{M} +C \pmod{M}$$? Does the equality hold true?
-3
votes
2answers
227 views

How can I solve $4x + 51y = 9$ using congruences?

I'm given: $4x+51y=9$. I am given a hint that when we use $4x=9 \pmod{51}$ we get $x = 15 + 15t$, and also if we use the congruence $51y=9 \pmod 4$ we get $y=3+4s$. They say it's handy to then find ...
1
vote
2answers
50 views

Find the lowest degree of the polynom $P$?

I have to determine the lowest degree of $P$ given by the following system : $\left\{ \begin{array}{l} P \equiv 2X \ \mod[X^2 -2X +1] \\ P \equiv 3X \ \mod[X^2 -4X+4] \end{array} \right.$ First, ...
2
votes
2answers
49 views

Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$

Question: Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$ First note that when $p$ is prime and $1\leq r\leq p-1$ the binomial coefficient $$\binom{p}{r}=\frac{p!}{r!(p-r)!}$$ is ...
1
vote
1answer
445 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
3
votes
1answer
39 views

Algebraic closure for rings

Is there any notion of algebraic closure for commutative rings? I am specifically interested in such a concept for $\mathbb Z_n$, with $n$ not a prime (possibly square-free). Such a concept would be ...
2
votes
2answers
37 views

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $ 3x - y = 1$; $2x + 3y = 0$

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $3x - y = 1$; $2x + 3y = 0$. Thank you.
-1
votes
0answers
13 views

If the euclidean algorithm is used to solve an equation ( i.e., $ax = b \mod(z)$) is the solution unique?

I have solved such an equation using the euclidean algorithm. However, unlike other methods, this gives one solution. Is this just one solution or the only solution. Help is much appreciated. Thank ...
-3
votes
1answer
29 views

Modular arithmetic equivalent [closed]

Let $A, B, C$ are integers from $1$ to $9$. In order to get an integer from this operation, A*B/C, I've devised two formulas. $(A*B) \pmod C$. $(A \pmod C)$ or $(B \pmod C)$. These two are not ...
2
votes
3answers
30 views

Simple mod 7 problem

I need to Show that $7x^3 + 2 = y^3$ has no solutions in integers x and y. The solution I am given is: Suppose there are solutions to this equation. Then mod 7 we have $2 ≡ y^3$ (mod $7$) and hence ...
1
vote
2answers
25 views

Sequence of perfect squares

Let $a,b\in \mathbb{N}$. Prove that, if $a$ is quadratic residue modulo $b$, then sequence $(a+kb)$, $k\in \mathbb{N}$, has infinite amount of perfect squares. How should I approach this ...
7
votes
2answers
112 views

Prove: if $n\mid 7^n+6^n$ and $n>1$, then $13\mid n$

Prove: if $n\mid 7^n+6^n$ and $n>1$, then $13\mid n$ Let $p$ be the least prime number such that $p\mid n$. And I want to show that $p=13$ Let $d$ be the least number such that: $14^d\equiv 0 ...
0
votes
3answers
47 views

Congruence $320 \equiv 1 (\text{mod }x)$ [closed]

I have the following congruence $320 \equiv 1 (\text{mod }x)$ And the question is : find all the modulos $x$ that make this congruence true.
1
vote
1answer
27 views

Standard definition for $a$ being congurent to $b$ mod $n$

My text puts the definition for $$a\equiv b \bmod n$$ as $$n\mid(a-b).$$ On the other hand, certain sources puts the definition as $$n\mid(b-a).$$ Which exactly is the standard notation or is there a ...
3
votes
2answers
198 views

How to calculate a Modulo?

I really can't get my head around this "modulo" thing. Can someone show me a general step-by-step procedure on how I would be able to find out the 5 modulo 10, or 10 modulo 5. Also, what does this ...
1
vote
1answer
321 views

Modulus Cancellation Law

I'm trying to understand the proof for cancellation law in modulus which states that: ...
15
votes
5answers
1k views

Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...
1
vote
1answer
39 views

how to solve system of quadratic equations (mod N)

Given a two equations: $${(ax_1 + b)}^2 = c_1 \pmod N$$ $${(ax_2 + b)}^2 = c_2 \pmod N$$ $N=p.q$ $p$ and $q$ are large primes $x_1, x_2$ and $c_1, c_2$ are known Is it computationally feasible to ...
0
votes
0answers
15 views

Showing irreducibility of polynomials of degree 3 over the rationals

Let $\ g = X^3\ -9X + 16 $. Prove that $g$ is irreducible over the rational numbers. So far I have used reduction modulo $5$ and this gives $g_5 = X^3 +X + 1$. Then I get $$ g_5(0) \equiv 1 \pmod5,\\ ...
5
votes
3answers
52 views

$a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 ...
3
votes
0answers
16 views

System of linear congruence, not relatively prime

Consider we have the following set of congruences $$x\equiv b_i \pmod {m_i}$$ for all $1\leq i\leq d$. $m_i$'s doesn't have to be relatively prime, so the Chinese remainder theorem doesn't work here. ...
1
vote
2answers
32 views

Equality symbols in modular arithmetic

E.g., can I write $(a^{p})^{2p} \equiv a^{2p}=a^pa^p\equiv aa\equiv a^2\pmod{\! p}$? I often see equality symbols inbetween mod equivalences. The equality signs point out the equality is not ...
0
votes
1answer
401 views

What will be the multiplicative inverse of square root of 5 with respect to a natural number $M$?

Can such a number $N$ be found such that $\sqrt{5}N \equiv 1 \mod M$? If no,what can be the best approximation for $N$?
-2
votes
1answer
48 views

Examples of methods for solving modular equations

Simple mod questions. Can you show example to do such things? $x+40 \equiv 1 \pmod{88}$. $x \cdot 40 \equiv 1 \pmod{88}$. $5a+3b \equiv 1 \pmod{11}$ and $2a+b \equiv 7 \pmod{11}$. Thank you.
0
votes
5answers
70 views

Prove that $n^3=n \text{ mod }6$ for every integer $n$. [duplicate]

Prove that for every integer $n$ , $n^3=n \text{ mod }6$ I was having no clue how to do this, then I thought of case-by-case analysis and obviously it worked. The problem is that there were six case ...
0
votes
0answers
20 views

Proof of an congruence modulo n [duplicate]

I've the following theorem: For $n\in\Bbb Z$, prove that $n^3\equiv n \pmod{6}$ Please check whether I produced a good proof: 1) Let $k,n\in\Bbb Z$ s.t. $6=kn$ since $n^{3}$ is congruent to $n ...
1
vote
1answer
72 views

Solving to find the general equation with a “mod” equation

They probably aren't called "mod" equation but i couldn't think how else to word them, so I have this equation $8x + 10y ≡ 8 \pmod 7$ And have been tasked with finding the general solution, I know ...
2
votes
2answers
610 views

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$

Prove that $x^3 \equiv x \bmod 6$ for all integers $x$ I think I got it, but is this proof correct? We can write any integer x in the form: $x = 6k, x = 6k + 1, x = 6k + 2, x = 6k + 3, x = 6k + ...
1
vote
2answers
20 views

Proof of a congruence relation

Let n∈N, and let a,b∈Z. Suppose that a≡b (mod n). Prove that n|a if and only if n|b. As can be proceed?
1
vote
2answers
19 views

Equivalence classes in $\mathbb{Z}_n$

I've the following exercise: Solve each of the following equations in the given set $\mathbb{Z}_n$: 1) $[5]+x=[1]$ in $\mathbb{Z}_9$ 2) $[2]\cdot x=[7]$ in $\mathbb{Z}_{11}$ For 1), is $x=5$ ...
1
vote
3answers
99 views

If $p$ is a prime number greater than $2$ and $k$ is a natural number so that $k<p$, how can I prove that?

If $p$ is a prime number greater than 2 and $k\in \mathbb{N}$ so that $k < p$, how can I prove that $p\choose k$ is congruent to $0 \bmod p$?
0
votes
2answers
24 views

Two real numbers which belong to distinct classes in the quotient group $\mathbb R/\mathbb Z$.

Let $x,y$ two real numbers. What does mean, in "pratical terms", that "$x,y$ belong to distinct classes in the quotient group $\mathbb R/\mathbb Z$"? Maybe that their difference $x-y$ isn't an integer ...
4
votes
3answers
54 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
2
votes
1answer
43 views

Sequence of real numbers which are distinct modulo 1.

Let $\{x_n\}_{n\in\mathbb N}$ a sequence of real numbers which are distinct modulo 1. Are the sequences $$\{\varepsilon x_n\}_{n\in\mathbb N} \ \ (\varepsilon\rightarrow 0), \ \ \ ...
1
vote
1answer
52 views

Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ ...
2
votes
3answers
116 views

Modular congruence, splitting a modulo

I can't find out, how to solve this. Will you give me some advice what to do in 4th step? Lot of thanks. This is my example: $7^{30}\equiv x\pmod{ 100}$ I want to compute it this way. These are my ...
2
votes
2answers
62 views

Number of fingers of a Martian

I have a question about what seems to be modular arithmetic, but I can't quite get the answer. The problem goes along the lines of: It is often said Earthlings use the decimal system because they ...