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
2answers
46 views

Solving a quadratic relation mod $13$

Solve for $x$ in $x^2 +2x +1\equiv 2 \pmod{13}$ I started with $2^{12}\equiv 1 \pmod{13}$ by Fermat's Little Theorem. I found no square root of $2$ from $(x+1)^2\equiv 2 \pmod{13}$ using a ...
1
vote
1answer
33 views

What's the remainder when $100!+5400$ is divided by $124$?

I'm pretty much stuck on this one because of the factorial. In this case, how can I solve it?
1
vote
1answer
41 views

How to describe $\#\{0\leq x<n:\gcd(x,n) \text{ is prime}\}$ the primes in $\mathbb{Z}/(n)$.

The above set actually comes from the following: In $\mathbb{Z}/(n)$ an ideal is prime if it is generated by an element $x$ such that for the integer representative $x$ we have $\gcd(x,n)=p$. To see ...
1
vote
3answers
52 views

Solutions of $y^2 = \alpha$ in $\mathbb{F}_{19}$

So I'm working on an exercise for elliptic curves and in one of my steps I have to determine all numbers $y \in \mathbb{F}_{19}$ for which it holds that $y^2 = \alpha$, with $\alpha \in ...
8
votes
2answers
84 views

Why does $\{1 \dots 9\}$ behave like this under multiplication mod $10$?

When I multiply the set $$\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$$ by $2$ and take the remainder mod $10$, I get the following repeated pattern. $$\{2, 4, 6, 8, 0, 2, 4, 6, 8\}$$ Multiplication by any even ...
0
votes
1answer
40 views

Multiplication modulo $n$

I encountered the following basic encryption scheme while studying MIT OCW's 6.042 course: Exchange a public prime $p$ and a secret prime $k'$. Encryption: Compute $m'=rem(mk, p)$ ...
2
votes
1answer
52 views

Is equivalent this expression to Wilson's theorem?

According to Wilson's theorem, $n$ is prime if and only if (1): $$(n-1)! \equiv -1 \pmod{n}$$ Would the following expression be valid and equivalent? (2) ...
1
vote
1answer
46 views

How to calculate the gcd of two polynomials $\mod 7$

I need to find gcd of $x^4-3x^3-2x+6$ and $x^3-5x^2+6x+7$ in $\mathbb Z/7 \mathbb Z[x]$, the integer polynomials mod $7$. Please any help will be appreciated.
2
votes
1answer
31 views

Solving a linear congruence

Use Euclids algorithm to find the multiplicative inverse of 11 modulo 59 and hence solve the linear congruence: $11x \equiv 8 \mod59$ My working so far.... $ {11v + 51w = 1}$ Using Euclid's ...
0
votes
3answers
55 views

What does the number must contain a value that is modulo X mean?

I get the basic concept of modulo: two numbers divided, the modulo is the remainder of the division... However, looking at a embedded systems manual: "all pointer parameters must contain an ...
6
votes
2answers
133 views

Is $y^2=x^3+7$ unsolvable modulo some $n$?

The equation $y^2=4x^3+7$ has no integral solution since $y^2\equiv4x^3+7\pmod4$ has no solution (i.e. has no solution in $\Bbb{Z}/4\Bbb{Z}$). It is well known that $y^2=x^3+7$ has no integral ...
1
vote
1answer
314 views

What meaning could possibly $m\simeq_{prim}n$ have?

For positive integers, what does $m\simeq_{prim}n$ means? I have this: Let $\alpha\in\mathbb Z \wedge n\;$ positive integer. If $\alpha\simeq_{prim}n$, then ...
11
votes
1answer
184 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
1
vote
1answer
53 views

Find all natural solutions to $x^2+2y^2 = z^2$ [duplicate]

I need to find all natural solutions to $x^2 + 2y^2 = z^2$ What I tried: I did $\pmod 2$ to the equation receiving $z^2 - x^2 \equiv 0 \pmod 2$. Then there are two possibilities: $x^2 \equiv 0 ...
2
votes
6answers
67 views

find all natural solution that satisfy $x^2+y^2 = 3z^2$

I need to find all natural $x,y,z$ that satisfy the following $x^2+y^2 = 3z^2$ $(0,0,0)$ is an answer of course. What I tried: I tried solving with congruences. I know that every square number ...
-1
votes
1answer
62 views

Inverse modulo without brute force [closed]

I have this piece of code and I want to know 'x' before the loop without brute force. Is there a way to do an inverse modulo or something? ...
0
votes
1answer
34 views

Why is $(p-2)! \textrm{ mod } p$ always 1 if $p$ is prime?

After running some test on my computer I found that when you have a prime $p$, then $(p-1)! \textrm{ mod } p$ always equals to $p-1$ and that $(p-2)! \textrm{ mod } p$ always equals to $1$. Why is ...
5
votes
1answer
59 views

Chinese reminder Theorem and primitive roots

The problem I am working on is "Let $p$ be a prime such that $p\equiv 1\pmod{105}$. Show that there exist integers $n, x, y, z$ such that $p$ does not divide $n$ and $n \equiv 3x^3 \equiv 5y^5 \equiv ...
1
vote
2answers
25 views

Computing $x \pmod 5$ if we only know $x \pmod 7$

Let's say we have a number $n$ of which I know its value $x$ modulo $k$, then how can I calculate its value modulo $l$? For example; $n=271, k=7$, and $l=8$, so $x=271 \textrm{ mod } 7=5$. How can I ...
0
votes
2answers
60 views

(603 · 6004 + 60005) mod 6 is equal to?

Any help here? i have an upcoming exam, and the question in some of the exercises that im practicing on are (603 · 6004 + 60005) mod 6 is equal I just dont understand how to do it. The way i saw it ...
0
votes
0answers
27 views

Some problems with modulo

Let $m$ be any natural number and define $$ \omega_n=\alpha_{n'}~\text{for }\lvert n'\rvert\leqslant m,~n'=n~(\text{mod }2m+1). $$ What does that mean? It is said that the sequence ...
1
vote
4answers
33 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
74 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
56 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
35 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
91 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
40 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
22 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
6 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
59 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
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
51 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
40 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
29 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
53 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
54 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
45 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
118 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
53 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
159 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
71 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
114 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
23 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
60 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
35 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
53 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
82 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
58 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