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
71 views

How can I find the remainder?

How can I find the remainder when $$(12371^{56}+34)^{28}$$ is divided by $111$. I have tried congruences modulo $111$ but without any success.
2
votes
1answer
84 views

Why is $x^{100} = 1 \mod 1000$ if $x < 1000$ and $\gcd (x,1000) = 1$?

Let $U(1000) =$ the multiplicative group of all integers less than and relative prime to $1000$. "Show that for every $x \in U(1000)$ it is true that $x^{100} = 1 \mod 1000$." Been thinking ...
1
vote
3answers
111 views

What is the relation between the linear combination and modular arithmetic?

What is the relation between the linear combination and modular arithmetic? The linear combination is in a field and there must be some fundamental relation between them. What is it?
0
votes
3answers
45 views

Is it true that $x \nmid (q-1) \implies 2^x \not \equiv 1 \mod q$

If $q$ is a prime number, then from little fermat theorem it is known that $$2^{q-1} \equiv 1 \mod q$$ My doubt is that If $x \nmid (q-1)$ then $2^x \not \equiv 1 \mod q$ is true statement or not?
0
votes
3answers
71 views

binary representation of integers congruent 1 and 3 modulo 4

Let $k=b_nb_{n-1}\ldots b_3b_2b_1b_0$ be the binary representation of an odd positive integer. Prove: If $k\equiv 1 \mod 4$ then $b_1=0$. If $k\equiv 3 \mod 4$ then $b_1=1$. I think that to prove ...
2
votes
3answers
58 views

Let $z \in \Bbb Z_m$, when is $z^2 \equiv 1$?

Let $z \in \Bbb Z_m$. When is $z^2=1, (z\neq1)$? I know that for $m$ prime, $z=p-1$ is it's own inverse, but what about nonprime $m$? Is $p-1$ the only self inverse element in $\Bbb Z_p$ ?
-4
votes
2answers
69 views

Why is $a^{-1}$ mod $p$ equal to $a^{p-2}$ mod $p$? [closed]

Why is $a^{-1}$ mod $p$ equal to $a^{p-2}$ mod $p$ in modular arithmetic?
4
votes
3answers
77 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
179 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
201 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
101 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
46 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
82 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
88 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 $x(...
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 \pmod{\!...
0
votes
2answers
509 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
69 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
58 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 counter-...
3
votes
2answers
96 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
189 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
106 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
127 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
33 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
51 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 $\langle\mathbb{Z}_n,\oplus\rangle$...
1
vote
1answer
59 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
41 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 table. ...
1
vote
1answer
39 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 \mathbb{F}_{19}...
8
votes
2answers
107 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
45 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\equiv-\frac{1}{(n-1)!}\pmod{\frac{n}{(...
1
vote
1answer
93 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
184 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 $\alpha^{-1}\equiv\alpha^{\varphi(n)-1}$(...
11
votes
1answer
282 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 2,...
0
votes
1answer
84 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
79 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 is ...
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
96 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
81 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 ...