# Tagged Questions

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$.

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.
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 ...
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?
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?
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 ...
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$ ?
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?
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$
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 ...
201 views

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.
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 ...
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 ...
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 ...
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}$(...
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,...
84 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 ...