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

Simple mod problem

It’s kind of a silly question but I can't find a simple way for finding the value of variable $d$ . $(5*d) \mod 8 = 1$ I normally just do this recursively by saying $d=d+1$ until I get the right ...
1
vote
5answers
78 views

Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$

Show that $a^{25} \pmod{88}$ is congruent with $ a^{5} \pmod {88}.$ I have proved it in the case that $\gcd(88,a)=1$, but in the other case , I don't know it. Any ideas?
1
vote
5answers
64 views

Calculate $2008!\pmod {2011}$

I think you should use the theorem of Wilson, because 2011 is a prime number. But I don't know how to use it. Thanks
1
vote
2answers
47 views

Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and > $p$, find one possible value of $x$.

The exercise verbatim: Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and $p$, find one possible value of $x$. (Hint: Write $p$ as $p = 4k +3$ and use Euler's Criterion. You ...
1
vote
4answers
99 views

Modular arithmetic , calculate $54^{2013}\pmod{280}$.

How do you calculate: $54^{2013}\pmod{280}$? I'm stuck because $\gcd(54,280)$ is not $1$. Thanks.
1
vote
0answers
47 views

Solving for $m$ algebraically given $m^e \equiv c_1 \pmod n$ and $(\alpha m+\beta)^e \equiv c_2 \pmod n$

Given $m,n,e,c_1,c_2,\alpha,\beta \in \mathbb{N}$ and the system of congruences: $$ \begin{align} m^e \equiv c_1 &\pmod n &(1)\\ (\alpha m+\beta)^e \equiv c_2 &\pmod n &(2) \end{align} ...
1
vote
1answer
30 views

How can I solve for P in the integer equation: $d = \frac{mNP+1}{B}$

How can I solve for P in the equation: $d = \frac{mNP+1}{B}$, where $P$ is the smallest integer $> 0$ such that $d$ is an integer? $m, N$ and $B$ are positive integers. They are usually quite ...
0
votes
0answers
9 views

Order of $B$ modulo $p^h$

Let $B$ and $p$ relatively primes and $e=\operatorname{ord}_p(B)$. How can I show that for $h\geqslant 0$, $\operatorname{ord}_{p^h}(B)=ep^g$, where $g=g(h)$? I've been trying using the fact that ...
-2
votes
2answers
71 views

Why modulo prime prefered over modulo composite?

In encryption process(aes encryption)and also in Galois field, a prime number is always used to perform the modulo operation. So I wanted to know the reason for using only prime numbers for modulo ...
2
votes
4answers
74 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 ...
0
votes
3answers
53 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
43 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
39 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
2answers
196 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
109 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
50 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
161 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
83 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
68 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
187 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
53 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
79 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
201 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
28 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
68 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
40 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
96 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: ...
3
votes
2answers
114 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
219 views

Modulo 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
223 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
155 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
56 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
56 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
88 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
47 views

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

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
31 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
109 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 ...
10
votes
2answers
249 views

$1989 \mid 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\mid 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 ...
1
vote
2answers
38 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
138 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
61 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
29 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 ...
4
votes
3answers
29k 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
39 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
66 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
78 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
70 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
112 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!
1
vote
2answers
25 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
22 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$ ...