Solve or prove there are no sltns mod problem.

[sg001]

Homework Statement

111x congruent to 75 (mod 321)

Homework Equations

The Attempt at a Solution

well I have been previously been doing these by exhaustioon of cases but that has been because I only have small mods ie,7

But I can't consider all cases for this large mod... what do I do?
dont need an answer but an explenation would be great!

Thanks

 

[Robert1986]

Well, there's an easy theorem that would allow you to know if this has any solutions without having to do much work. You probably aren't allowed to use it, but if you are, here it is:

Let a,b,m be integers such that m>0 and (a,m) = d. If d \nmid b then ax \equiv b \pmod{m} has no solutions. If d | b then ax \equiv b \pmod{m} has exactly d soultions modulo m.

(This was taken from Ken Rosen's book.)

Now, if you can't use that theorem, here is something that should work.

What is it exactly that you want to know? That is, what does it mean for two numbers to be congruent modulo some number? For example, if a \equiv b \pmod{m} what does that tell you about the relationship between a-b and m? Now, what if you had ax \equiv b \pmod{m}? What would this tell you about the relationship between ax - b and m? Now, do you see anything familiar? In particular, can you somehow make this congruence look like a linear Diophantine equation?

 

[sg001]

Well, there's an easy theorem that would allow you to know if this has any solutions without having to do much work. You probably aren't allowed to use it, but if you are, here it is:

Let a,b,m be integers such that m>0 and (a,m) = d. If d \nmid b then ax \equiv b \pmod{m} has no solutions. If d | b then ax \equiv b \pmod{m} has exactly d soultions modulo m.

(This was taken from Ken Rosen's book.)

Now, if you can't use that theorem, here is something that should work.

What is it exactly that you want to know? That is, what does it mean for two numbers to be
congruent modulo some number? For example, if a \equiv b \pmod{m} what does that tell you about the relationship between a-b and m? Now, what if you had ax \equiv b \pmod{m}? What would this tell you about the relationship between ax - b and m? Now, do you see anything familiar? In particular, can you somehow make this congruence look like a linear Diophantine equation?

Ok thanks, so with the second method

ax -b/m... but then it does not get me any where with a large modulus,,, am I missing something?

and for the first method I think I get it, but is d the gcd of (a,m)...

would you mind applying this first method to a simple example, thanks!

 

[HallsofIvy]

If 111x= 75 (mod 321) then there exist an integer, y, such that 111x= 75+ 321y or
111x- 321y= 75. Since each term is divisible by 3, divide through by 3 to simplify to 37x- 107y= 25. That's a linear Diophantine equation that can be solved using the "Euclidean division algorithm".

37 divides into 107 twice with remainder 33. 33= 107- 2(37).
33 divides into 37 once with remainder 4. 4= 37- 33.
4 divides into 33 8 times with remainder 1: 1= 33- 8(4).

Replace the "4" in that last equation with 37- 33 from the previous equation:
1= 33- 8(37- 33)= 9(33)- 8(37)
Replace the "33" in that equation by 107- 2(37):
1= 9(107- 2(37)- 8(37)= 9(107)- 26(37).

You can check that arithmetically: 9(107)= 963 and 26(37)= 962.

Now multiply by 25: 25= 225(107)- 650(37). That is, one solution to 37x- 107y= 25 is x= -650, y= -225. Of course, we want solutions between 0 and 321. We use thefact that it is also true that x= -650+ 107k, y= -225+ 37k is also a solution for all k: 37(-650- 107k)- 107(-225+ 37k)= -24050+ (37)(107k)+ 24075- (107)(37k)= 25 for all k. So we choose k to make both positive: 107 divides into 650 6 times with a remainder and 37 divides into 225 5 times with a remainder- taking k= 7 gives
x= -650+ 107(7)= 99 and y= -225+ 37(7)= 34.

Checking: 111(99)= 10989. 321 divides into that 34 times with remainder 75.
111(99)= 75 (mod 321).

 

[Robert1986]

Let's look at the second method. You want to find an x such that 111x \equiv 75 \pmod{321}, right? Now, what does this mean, exactly? Well, if there is such an x then there exists a y such that 111x - 75 = 321y, right? Now, let's re-write this as: 111x - 321y = 75. This is a linear Diophantine equation and I'm sure you have had some sort of theorem that tells you when there are solutions to this equation. It will involve finding the gcd of 111 and 321, which isn't hard.

Consider the equation 37x \equiv 25 \pmod{107}.

For the first method, a = 37 and m = 107. We have that (37,107) = 1. Since (37,107)=1|25 there are infinitely many solutions. Now, as I said, I would guess that you are not allowed to use this theorem, but by all means use it if you can. If not, then do it the linear Diophantine equation way I showed above.