Questions tagged [modular-arithmetic]

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

Modular arithmetic (clock arithmetic) is a system of arithmetic of integers. The basic ingredient is the congruence relation $a \equiv b \bmod n$ which means that $n$ divides $a-b$. In modular arithmetic, one can add, subtract, multiply, and exponentiate but not divide in general. The Euclidean Algorithm, the Chinese Remainder Theorem, and Fermat's Little Theorem are important throughout mathematics. Modular exponentiation plays an important role in cryptography nowadays.

11320 questions
0
votes
1 answer

Let $a, b$ and $m$ be integers, and $m \ge 2, \ ab ≡ [ (a \bmod m) * (b \bmod m) ] (\bmod m).$

I'm relatively new to this, I got no idea how to proceed at all. I'm just bad at this chapter :( $$ m\mid (ab- (a \bmod m \cdot b \bmod m)). $$ How do I proceed after that? Is this even the first step?
0
votes
1 answer

How many solutions to the equation $C \equiv M^e \;(\mbox{mod}\;n)$?

Fix $n,e\in \mathbb{Z}$ and let $C\in\mathbb{Z}_n$. How many solutions $M\in \mathbb{Z}_n$ do I have to the equation $$C \equiv M^e \;(\mbox{mod}\;n)\;?$$ This question arose from trying to solve the equation $$11\equiv…
UserA
  • 1,650
0
votes
4 answers

Solving $39x\equiv75\pmod{102}$

Decide if a solution to the congruence $39x\equiv75\pmod{102}$ exists. As $\operatorname{hcf}(39,102)=3$ we can write the congruence as $13x\equiv25\pmod{34}$. Using Euclid's algorithm gives $1=5\cdot34-13\cdot13$. I don't get where to go from…
0
votes
1 answer

How to solve the number of solutions to a linear congruence modulo q?

How many $x$ less than or equal to $n$ are there when $x\equiv i(\text{mod }q) \equiv 0(\text{mod }p)$? I am just looking for an upper and lower bound.
0
votes
1 answer

Explicit solution to modular equation

I have the following modular equation, $$ (p + a) \mod 3 = m$$ which I want to solve for $a$. Of course, there are many valid values for $a$, but since I assume $m,p \in \{ 0, 1, 2\}$, I only want values of $a$ in that same range, in which case they…
0
votes
1 answer

Consecutive application of Modulo Operator

Is it true that $a \bmod n\equiv (a \bmod n)\bmod n$? Is is possible to show intuitively why ?
AleWolf
  • 185
0
votes
0 answers

Inverting exponentiation modulo a prime

Suppose $p$ is an odd prime, $g$ is a primitive root of $p$, where $i
0
votes
1 answer

Modulo division: Find all integers $k \geq 2$ such that $k^2 = 5k(\mod 15).$

Find all integers $k \geq 2$ such that $k^2 = 5k(\mod 15).$ Using arithmetic on $\mathbb{Z}_{15},$ $\bar{k}^2 = \bar{5}\bar{k},$ may I divide both sides by $\bar{k}$ to arrive at $\bar{k} = \bar{5}?$
0
votes
2 answers

For any integers $a$ and $b$, $ab = 0$ implies $a = 0$ or $b = 0$. Prove that this remains true mod prime numbers but not true mod a composite number.

I roughly understand modular arithmetic but I am having trouble starting the problem. I can prove it for just integers but I can't seem to relate it to mod primes and composites?
bow123
  • 53
  • 5
0
votes
2 answers

In $\Bbb{Z}/m\Bbb{Z}$, show that $([a]_m)^{qd+r} = (([a]_m)^d)^q([a]_m)^r$

In $\Bbb{Z}/m\Bbb{Z}$, show that $([a]_m)^{qd+r} = (([a]_m)^d)^q([a]_m)^r$. My first attempt at this question was to use simple arithmetic properties to prove this true, however, this is incorrect. What is the best way to prove this?
0
votes
1 answer

Help with a proof in modular arithmetic

Let $a,b,n \in Z$ with $n > 0$ and $a \equiv b \mod n$. Also, let $c_0,c_1,\ldots,c_k \in Z$. Show that : $c_0 + c_1a + \ldots + c_ka^k \equiv c_0 + c_1b + \ldots + c_kb^k \pmod n$. For the proof I tried : $a = b + ny$ for some $y \in Z$. If I…
0
votes
2 answers

Linear congruence $8x\equiv 21\pmod{24}$

$8x\equiv 21\pmod{24}$ I am having problem solving this linear congruence because 8 is even and 21 is odd.
0
votes
0 answers

Find the solutions of an equation in mod 8

find all solutions to each of the following equations: (a) $3x = 2$ mod 8 (b) $4x = 4$ mod 8 (c) $4x^2 = 4$ mod 8 (d) $4x + 4x^2 = 0$ mod 8 Those are my answers: a) $x=6$ b) $x=1 , x=3 , x=5, x=7$ c) $x=1 , x=3 , x=5, x=7$ d) $x=0, x=1 , x=2, x=3…
JOJO
  • 1,080
0
votes
1 answer

square ($a \bmod b$)

suppose $a = np +r$ where $n$ is an integer, $p$ is a prime, $r$ is the remainder. So, $ a \bmod b ≡ r$. Is $(a \bmod b)^2 = a^2 \bmod b^2$? I was told this is correct, and can't prove it. (I don't want $a^2 \bmod b$, I am aware they mean different…
Peter_Pan
  • 1,836
0
votes
2 answers

modular exponentiation $14^{20} \pmod{33}$

How do I find 14^20 mod 33 ? I tried writing 14^20 as 14^(2+4+8+6) but still no simplification. Should I just check all the power of 14 mod 33 and hope that some of them give nice numbers (1 or 2) What is a good method ?
lohey
  • 31