356 views

### Multiplicative Inverse for Elements in an Integer Ring [duplicate]

In the book I'm reading it says that there exist elements with multiplicative inverses in a integer ring if $gcd(a,m)=1$ where $a$ is the element and $m$ is the modulo. The inverse $a^{-1}$ is ...
168 views

### Solving congruence system with no multiplicative inverse [duplicate]

I am trying to find a way of solving congruence systems of the form: $$b*x = a \quad mod \quad y$$ Where $b$ and $y$ are not prime to each other. My current way of solving congruence systems ...
73 views

### Number of solutions to $89 x \equiv 7 \pmod{55}$ [duplicate]

How do I show that my solution to the congruence is the only solution? I'm asked to solve, $\mu,\lambda$ that satisfy $$89 \lambda+55 \mu=1$$ Using Euclid's algorithm I found $\lambda=-21,\mu=34$. ...
42 views

### Modulo arithmetic: finding “c” when result of right-hand side expression is a float [duplicate]

In my series of questions on modular arithmetic, I stumbled upon cases where normal textbooks don't explain much. Now my problem is to find $c$ when the expression to be solved (right-hand side) ...
56 views

### How many solutions are there to the equation $na\equiv _m0$ for $0\leq a <m$? [duplicate]

I'm reading trough a proof that the number of (group) homomorphisms $\mathbb{Z}_n\rightarrow \mathbb{Z}_m$ is $$\text{gcd}(n, m),$$ and this is the only step that I'm not understanding, namely, that ...
29 views

### If $x\equiv a\pmod{n}$, prove that either $x\equiv a\pmod{2n}$ or $x\equiv a+n\pmod{2n}.$ [duplicate]

If $x\equiv a\pmod{n}$, prove that either $x\equiv a\pmod{2n}$ or $x\equiv a+n\pmod{2n}.$ Well I am a bit stuck in this congruence problem. I tried out :- $n\vert x-a$ so for $2n|x-a$, $x-a$ must be ...
33 views

### Find the solutions to $4x \equiv 16 \pmod{20}$ [duplicate]

Find the solutions to $4x \equiv 16 \pmod{20}$ I managed to determine this by writing $4x = 16 + 20j \implies x =4 +5j \implies x \equiv 4 \pmod{5}$, but the official solution stated that the ...
45 views

### How to do division of two numbers which are already under modulo 'm'? [duplicate]

How to do division for the following example? Case 1 : Without modulo n1 = 40, n2 = 8 Quotient = n1/n2 = 5 Case 2 : With modulo m = 6 n1 = n1 mod m = 4 (AND) n2 = n2 mod m = 2 Quotient = 4 / 2 =...
1k views

### Solving $ax \equiv c \pmod b$ efficiently when $a,b$ are not coprime

I know how to compute modular multiplicative inverses for co-prime variables $a$ and $b$, but is there an efficient method for computing variable $x$ where $x < b$ and $a$ and $b$ are not co-prime, ...
1k views

1k views

### Existence & uniqueness of solutions of linear congruences $\ cx\equiv b\pmod m$

Prove that one can solve the congruence $cx \equiv b \pmod m \Longleftrightarrow \gcd(c,m)|b$. Show, moreover, that the answer is unique $\bmod{m/\gcd(c,m)}$ My Work Proof of $(\Rightarrow)$: ...
### $12x \equiv 33 \pmod{57}$ [closed]
Can you show me a step by step instruction how to solve this problem? $$12x \equiv 33 \pmod{57}$$