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

4
votes
3answers
76 views

Remainder when divided by 9

I'd like help with this question : What is the remainder when $$2^{2} + 22^{2} + 222^{2}+ \ldots + \underbrace{2222...22^{2}}_{49 \text{ times}} $$ is divided by $9$
6
votes
6answers
176 views

What are the last two digits of $77^{17}$?

I'm trying to solve current task referenced the following but I stuck at $\displaystyle77^{17}\equiv x\pmod{100}$. As it is described on above link it uses Binomial Theorem. But I read a lot about the ...
10
votes
0answers
193 views

Generalizing the Pell equation $x^2-61y^2 = 1$

In a table of fundamental solutions $f_1(x,y)$ to Pell equations, $$x^2-dy^2=1\tag1$$ with $d<110$, two will stand out, $$(U_{61})^6 = \big(\tfrac{39+5\sqrt{61}}{2}\big)^6 = x+y\sqrt{61} ...
3
votes
2answers
96 views

$x^2 + 3x + 7 \equiv 0 \pmod {37}$

I'm trying to solve the following $x^2 + 3x + 7 \equiv 0 \pmod {37}$ What I've tried - I've tried making the left side as a square and then I know how to solve but couldn't make it as a square ...
0
votes
1answer
45 views

What are the solutions of the equation $\phi (x) =p$ with p an prime number, x an integer and $\phi $ the Euler function.

What are the solutions of the equation $\phi (x) =p$ with p an prime number, x an integer and $\phi $ the Euler function. I have actually no idea how to start with solving this problem.
3
votes
3answers
81 views

Monic polynomial $= 0 \mod p$ for all $x$

For a monic polynomial with integer coefficients (leading coefficient of $1$) $f(x)$ where $f(x) \equiv 0$ mod $p$ for all $x$, where $p$ is a prime number how do I show that the degree of the ...
0
votes
2answers
84 views

solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$

I need to solve $3x^2 + 6x +1 \equiv 0 \pmod {19}$ I saw the same problem here - Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$ but didn't understand how he got to the conclusion ...
1
vote
4answers
131 views

Final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$

What are the three final numbers of $2003^{2003}$ and $2003^{2003^{2003}}$? Do I use the Chinese Remainder Theorem here, and if so, how?
0
votes
2answers
24 views

Prove $a,2a,\ldots,(p-1)a$ leave different remainders mod $p$

Say $p$ is a prime number and we have $a,2a,\ldots,(p-1)a$, if you then take any $ a \bmod p$ in the range of our $a$s they will all have different remainders, as long as $a$ is not $\equiv 0 ...
0
votes
2answers
507 views

Question of remainder on dividing by 7

Question : What is the remainder when $$ 10^{10} + 10^{10^2} +10^{10^3} + \ldots + 10^{10^{100}} $$ is divided by $7$?
1
vote
1answer
68 views

Finding modulo inverse if gcd is not 1

I have to find $$\frac{p^e-1}{p-1} \bmod 1000000007,$$ where $p$ is a prime number. If $\gcd(p-1,1000000007)$ is not $1$, since modular inverse of $p-1$ is not defined. Also, (p^e-1) is divisible by ...
-2
votes
1answer
55 views

Calculate (A / B) mod C [closed]

someone told me: (A / B) MOD C = ((A) MOD (B * C)) / B Is that right? I have tried some testcases and it turned out to be so Please prove or give me a ...
3
votes
2answers
87 views

Show that there are infinitely many integer solutions to the equation $x^3+y^5=z^7$

Show that there are infinitely many integers such that $$x^3+y^5=z^7$$ and where $x^3,y^5$ and $z^7$ are all non-zero and distinct. The hint suggests to look at solutions of simultaneous equation ...
0
votes
0answers
59 views

can two different binomial coefficient be equal mod a prime?

Given two primes $p$ and $q$ with $q >p$. Can it happen $$\binom{p}{a} \equiv \binom{p}{b}\pmod q$$ for $a$ and $b$ distinct integers between $0$ and $p-1$, and $a+b$ not equal to $p$? Can anyone ...
2
votes
3answers
185 views

Chinese remainder theorem - RSA

The following is a excerpt from RSA Decryption correctness proof (section 4) : $$\begin{align} C^d &\equiv M\pmod {p} \tag{1}\\ C^d &\equiv M\pmod {q} \tag{2} \end{align}$$ Now by the ...
5
votes
4answers
104 views

How do I calculate $2^{47} \pmod{\! 65}$?

I'm trying to calculate $2^{47}\pmod{\! 65}$, but I don't know how... I know that: $65=5\cdot 13$ and that: $2^{47}\equiv 3 \pmod{\! 5}$ and $2^{47}\equiv 7\pmod{\! 13}$... (I used Euler) But ...
0
votes
0answers
37 views

Can I solve this mathematically? $({x^7}\mod33)^d\mod33=x$

Can I find x or d value for $({x^7}\mod33)^d\mod33=x$? Or can I make at least some assumptions of range of those values? I ask for a mathematical way because that "33" usually is a number bigger ...
5
votes
2answers
126 views

Solve $x^8 \equiv 3 \pmod {13}$

I need to find all solutions to $x^8 \equiv 3 \pmod {13}$. What I've tried: I know $2$ is a primitive root modulo $13$. So it is equivalent to solve $2^{8t} \equiv 2^4 \pmod {13}$ Then I get $t = ...
1
vote
1answer
31 views

Using modular arithmetic to evaluate a modulo operation

I needed to evaluate $3^{100} \pmod 7$ by hand. So, I made a list of increasing powers of $3 \pmod 7$ like so: $3^1 \equiv 3 \pmod 7$ $3^2 \equiv 2 \pmod 7$ $3^3 \equiv 6 \pmod 7$ (1) ... $3^6 ...
2
votes
1answer
32 views

Solving for solutions to a congruence

I am interested in solutions to this congruence: $$2^kx \equiv x \bmod m$$ Where $m$ and $x$ are known positive integers. They may not necessarily be prime or coprime. I am looking for solutions for ...
-1
votes
1answer
40 views

How to perform modular

How do you solve this kind of mod when $x<n$ in $$x \bmod(n)$$ The other day I was looking at this $ 2 \bmod(7) = 2$ . How is this even possible since there will be no remainder or its always $0$ ...
1
vote
1answer
48 views

The generators of the group $\langle\mathbb{Z}_n,\oplus\rangle$ are all $g \in \mathbb{Z}_n $ for which $\gcd(g,n)=1$ [duplicate]

I'm trying to find a proof of this: The group $\langle\mathbb{Z}_n,\oplus\rangle$ is cyclic for every $n$, where $1$ is a generator. The generators of the group ...
1
vote
1answer
56 views

Clarification of a proof of Eisenstein's lemma

I'm working on a proof of quadratic reciprocity following Wikipedia's proof via Eisenstein, and one line in the proof seems unjustified: On the other hand, by the definition of $r(u)$ and the ...
2
votes
1answer
40 views

how to get maple to do linear algebra in Z_2 (integers modulo 2)

how to get maple to do linear algebra in Z_2 (integers modulo 2) I don't want it to solve and then reduce mod 2 I want it to work over Z_2 so basis([ [1,1,1], [1,-1,1 ]) = [1,1,1] If this is ...
0
votes
2answers
47 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
38 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
46 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
53 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
105 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
44 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
55 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
90 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
46 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
65 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
180 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
318 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
280 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 ...
0
votes
1answer
81 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
78 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 ...
0
votes
1answer
37 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
93 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
76 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
29 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
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} ...