remodularization? help?

[oliver$]

i'm not sure if i understand this concept at all.
for finding all the solutions (mod 45) of

4x=7 (mod 45), we know that solutions exist, b/c the gcd (4, 45)=1 which divides 7.
then
4x= [52,97,112,157] (mod 45*4)
4x= 52 (mod 180) and 4x=112(mod 180).
these reduce to x=13 (mod 45) and x=28 (mod 45) respectively.
then x=13, 28 (mod 45)?

i feel like i'm missing some important step or piece of the concept.

[matt grime]

There is certainly something you've not quite grasped. In particular you may not say that since

a=b mod p

then

a=b+rp mod ap


this just is not going to help even if it were true, which it isn't guaranteed to be, though by some *fluke* it may give an answer.

What you need to do is find the multiplicatice inverse of 4 modulo 45.

since 4*11=-1 mod 45

you should be able to solve it from there.

[oliver$]

i tried it your way, finding the multiplicative inverse, and got x=13.

Then I tried my method with 4x= 0 (mod 45) to get x=0, which works with your method as well. i don't know where i got the formula. but thank you. i'd rather do the problem right than do it by fluke.

[matt grime]

You've just introduced new answers - a little like squaring. I've not chekced to see if your method must produce the correct answer, but it vertainly must produce incorrect ones, and it isn't nec. clear whioh of them is or insn't going to be correct without substituting back.

To find multiplicative inverses one only needs to use eulcid's algorithm.