More congruence trouble

**Nerdfighter** · June 1st 2009, 02:18 PM

for which integers $c$ with $0 \leq c < 1001$ does the congruence $154x \equiv c$ $(\bmod 1001)$ have solutions? For each case when there are solutions, find how many solutions are not congruent modulo 1001.

Originally, I thought this problem might have something to do with multiplicative inverses, but I didn't get anywhere on that front.

If it matters, I calculated $\gcd (154,1001)$ to be 77.

**chiph588@** · June 1st 2009, 04:13 PM

$ax \equiv b \mod n$ has a solution iff $(a,n) \mid b$ . So $154x \equiv c \mod 1001$ is solvable iff $(154,1001)=77 \mid c$ .
Therefore $c = 77n, \; n \in \mathbb{N}$ .

**Moo** · June 2nd 2009, 11:57 PM

Originally Posted by chiph588@

$ax \equiv b \mod n$ has a solution iff $(a,n) \mid b$ . So $154x \equiv c \mod 1001$ is solvable iff $(154,1001)=77 \mid c$ .
Therefore $c = 77n, \; n \in \mathbb{N}$ .

Since we're working with modulos, I would say that it's 77n mod 1001.

And since 1001/77=13, there are 13 different values for c...

Thread: More congruence trouble

LinkBack

Thread Tools

Display

More congruence trouble

Similar Math Help Forum Discussions

[SOLVED] congruence

[SOLVED] More Congruence

Congruence

Congruence

congruence and gcd

Search Tags