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

Prove that $x^2 \equiv y^2 \pmod p$ if and only if $x \equiv y \pmod p$ or $x \equiv -y \pmod p$. Hint: $x^2-y^2 = (x+y)(x-y)$.

This is the exercise verbatim: An integer n is a square modulo p if there exists another integer x such that $n \equiv x^2 \pmod p$. Prove that $x^2 \equiv y^2 \pmod p$ if and only if $x \equiv y ...
2
votes
3answers
50 views

Modular arithmetic: How do resolve it? [closed]

How do resolve this modular arithmetic: $$7^3\pmod {55} \equiv \ ?$$ Please provide every step to arrive at the solution.
0
votes
1answer
39 views

$ P\mid n \implies \exists (a,b)\in\mathbb{Z}^2 \quad an+b(p-1)=1$

show that $$ p\mid n \implies \exists (a,b)\in\mathbb{Z}^2 \quad an+b(p-1)=1$$ with p is the least prime dividing my attempts Indeed, Let $d=n\wedge (p-1)=gcd(n,p-1)$ and we try to show ...
2
votes
2answers
28 views

Can the concept of congruence be applied to the remainder of a polynomial division?

I know this is a very simple question, so please I apologize but I am not familiar with it: Can the concept of (modular arithmetic) congruence be applied to the remainder of a polynomial ...
0
votes
0answers
48 views

Use Euler's theorem to find the inverse of 17 modulo 31 in the range {1,…,30}.

This is a question from the MIT opencourseware Mathematics for Computer Science, problem set 3: Use Euler's theorem to find the inverse of $17$ modulo $31$ in the range $\{1,...,30\}$. I don't seem ...
2
votes
2answers
49 views

Finding the smallest divisor

Find the smallest divisor of $ 12!+6!+12!\cdots6!+1!$ except 1 I know this has to do something with Wilson's theorem which states the if $n$ is a prime number $n$ will divide $(n-1)!+1$.
3
votes
2answers
44 views

$2009^{2007} \equiv x \pmod {2012}$ Dealing with mods of fractions?

$$2009^{2007} \equiv x \pmod {2012}$$ Now I used Fermat's theorem in this case and got $2009^{1004} \equiv 1$ or further $2009^{2008} \equiv 1$ Now this overshoots the exponent I need, so after ...
4
votes
6answers
116 views

Last 2 digits of $9^{1500}$

I've read this PDF where it explains how to find the last digit of a number. If I were to find the last digit of $9^{1500}$ I would simply write it as $(3^{2})^{1500}$ and then use the patterns in ...
-1
votes
1answer
51 views

Fraction modulo integer in sage [closed]

I'm working on a sage script right now, I have some polynomials coefficients that are rational, and I want to apply a congruence on these coefficientss, for example: $p = 1 + (7/2)x$ the function ...
1
vote
3answers
66 views

Find $y$ satisfying $17y = 1 \mod (130)$

Let $x=17$ $n=130$. Find $y; (1\leq y \leq n-1)$ that satisfies :$$xy=1 \pmod n$$ Now I'm not sure if I should use one of Euler's theorem's for prime numbers? Can anyone help? Or try something with ...
6
votes
1answer
149 views

Test about prime gaps: which conclusions can be drawn from the results?

I did the following test: For every prime, take the prime gap distance $dp$ to the previous prime and the next prime $dn$, then calculate $a=(pp\ mod\ dp)$ and $b=(np\ mod\ dn)$. If $a$ or $b$ ...
3
votes
1answer
34 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 ...
3
votes
4answers
67 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} = ...
5
votes
3answers
112 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 ...
2
votes
1answer
22 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
54 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
1answer
33 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
51 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: ...
2
votes
2answers
81 views

Solving $3x^3\equiv 7\pmod{925}$

I am trying to solve $3x^3\equiv 7\pmod{925}$. I thought of using brute force, but $925$ is too big for that. I also tried raising both sides of the equation to the power of $3$, but it didn't help. ...
0
votes
0answers
50 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
119 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 ...
2
votes
1answer
34 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?
2
votes
2answers
53 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
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, ...
3
votes
1answer
57 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
39 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.
0
votes
1answer
23 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 ...
2
votes
3answers
37 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 ...
6
votes
1answer
136 views

$1989|n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

Before anyone comments, yes this is kind of a duplicate of Prove that $1989|n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants to ...
1
vote
2answers
26 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
118 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
54 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
28 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
3answers
945 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 ...
0
votes
0answers
16 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
55 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 ...
1
vote
2answers
48 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 ...
3
votes
0answers
25 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. ...
2
votes
3answers
102 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!
0
votes
0answers
21 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
2answers
21 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$ ...
0
votes
5answers
78 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
2answers
27 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
67 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]$, ...
1
vote
1answer
83 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
1answer
46 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), \ \ \ ...
3
votes
4answers
80 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 ...
2
votes
1answer
69 views

What is $13^{498}$ (mod $997$)? [duplicate]

I have to determine $$13^{498} \pmod{997}$$ I know that it can only be $1$ or $-1$. But I don't quite know which. How can I decide?
1
vote
1answer
68 views

Modulus differentiation

For a Java project, I need to find a way to compute the derivate of a modulus function like $$f(x) = g(x) \pmod{h(x)}$$ for any value of $x$. I know that the modulus function is discontinuous. If ...