Ax≡ay (mod m) iff x≡y (mod m/(a,m))

[kingwinner]

note: (a,m)=gcd(a,m)

Theorem: ax≡ay (mod m) if and only if x≡y (mod m/(a,m))

And then in the middle of a certain proof later on, my textbook says:
Suppose (a,m)|b.
Then BY THE ABOVE THEOREM(?),
ax≡b (mod m) if and only if (a/(a,m))x ≡ b/(a,m) (mod m/(a,m))?

But I don't see exactly why the above theorem will give us this result.
First of all, I don't think on the RHS, b is necessarily a multiple of a.
Secondly, the theorem says we can divide the LHS and RHS by a (not (a,m)), and divide the modulus by (a,m), NOT a. But in that proof, they divide everything by (a,m) which is not what the theorem says.
Could someone please show me how to apply the theorem in a way that will lead us to this result? I really don't see how...

Is it also true that ax≡ay (mod m) if and only if
(a/(a,m))x ≡ (a/(a,m))y (mod m/(a,m))?

I'm confused...
I hope someone can explain this. Any help is much appreciated!

 

[HallsofIvy]

Apparently you are very confused! Are you clear on what modulo arithmetic itself is? You say " I don't think on the RHS, b is necessarily a multiple of a". Why would you expect it to be? Saying "ax= b (mod m)" does not imply that b is a multiple of 6. Only that ax-b is a multiple of n. For example, if a= 2, b= 5, and m= 7, ax= b (mod m) becomes 2x= 5 (mod 7). That is satisfied by x= 6 because 2(5)= 12= 5+ 7.

 

[ramsey2879]

note: (a,m)=gcd(a,m)

Theorem: ax≡ay (mod m) if and only if x≡y (mod m/(a,m))

And then in the middle of a certain proof later on, my textbook says:
Suppose (a,m)|b.
Then BY THE ABOVE THEOREM(?),
ax≡b (mod m) if and only if (a/(a,m))x ≡ b/(a,m) (mod m/(a,m))?

But I don't see exactly why the above theorem will give us this result.
First of all, I don't think on the RHS, b is necessarily a multiple of a.
Secondly, the theorem says we can divide the LHS and RHS by a (not (a,m)), and divide the modulus by (a,m), NOT a. But in that proof, they divide everything by (a,m) which is not what the theorem says.
Could someone please show me how to apply the theorem in a way that will lead us to this result? I really don't see how...

Is it also true that ax≡ay (mod m) if and only if
(a/(a,m))x ≡ (a/(a,m))y (mod m/(a,m))?

I'm confused...
I hope someone can explain this. Any help is much appreciated!

I think you should be aware that if a = 0 or a factor of m, then you cannot divide a out from the equation ax = ay mod m. For instance 0*5 = 0*7 mod 9 because 5 = 7 mod 1 ,i.e. mod (9/(0,9)) = mod (9/9) = mod 1 but 5 <> 7 mod 9

 

[kingwinner]

Apparently you are very confused! Are you clear on what modulo arithmetic itself is? You say " I don't think on the RHS, b is necessarily a multiple of a". Why would you expect it to be? Saying "ax= b (mod m)" does not imply that b is a multiple of 6. Only that ax-b is a multiple of n. For example, if a= 2, b= 5, and m= 7, ax= b (mod m) becomes 2x= 5 (mod 7). That is satisfied by x= 6 because 2(5)= 12= 5+ 7.

I understand what you're saying for sure.

But the theorem says:
ax≡ay (mod m) if and only if x≡y (mod m/(a,m)).

Firstly, our congruence a[/color]x≡b (mod m) here is not of the above form, so why is the theorem even applicable?

Secondly, the theorem doesn't say that we can divide the LHS and RHS and the modulus by (a,m). The theorem says that we can divide the LHS and RHS by "a", and divide the modulus by (a,m).

I hope this clarifies my quesiton.

 

[JSuarez]

Firstly, our congruence ax≡b (mod m) here is not of the above form

Actually, it is: you just have to write a=\left(a,m\right)\times a/\left(a,m/right) and
b=\left(a,m\right)\times b/\left(a,m/right).

And we may assume that b is divisible by (a,m) because, otherwise, the congruence

ax\equiv b\left({\rm mod}m)

will not have solutions.

 

[Hurkyl]

I understand what you're saying for sure.

But the theorem says:
ax≡ay (mod m) if and only if x≡y (mod m/(a,m)).

Firstly, our congruence a[/color]x≡b (mod m) here is not of the above form, so why is the theorem even applicable?

Actually, it is of that form. It's a little confusing because we're using the same variable names for multiple purposes, so let me color them:

ax[/color]=ay[/color] (mod m)
ax[/color]=b[/color] (mod m)​

One way to get a match is by assigning

a[/color] = 1
x[/color] = ax[/color]
y[/color] = b[/color]​

There are lots of trivial modifications you could make to allow you to match the desired form in other ways too.