# Solve or prove there are no sltns mod problem.

• sg001
In summary: When x and y are both positive, that is. So, we can rewrite that as:x=-321+107, y=325. checking: 111(325)= 10989.
sg001

## Homework Statement

111x congruent to 75 (mod 321)

## 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

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?

Last edited:
Robert1986 said:
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!

Last edited:
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).

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.

## Q1: What does it mean to solve or prove there are no solutions mod problem?

Solving or proving there are no solutions mod problem means finding a solution to a mathematical equation that satisfies the given conditions, or proving that no such solution exists.

## Q2: What is mod problem?

Mod problem, or modular arithmetic problem, is a mathematical equation that deals with remainders after division. It involves finding the remainder when a number is divided by another number.

## Q3: How do you approach solving or proving there are no solutions mod problem?

The approach to solving or proving there are no solutions mod problem depends on the specific problem. However, it often involves using mathematical techniques such as modular arithmetic, number theory, and logic to manipulate and analyze the given equation.

## Q4: Can there be multiple solutions to a mod problem?

Yes, there can be multiple solutions to a mod problem. In some cases, there may even be an infinite number of solutions. It depends on the specific equation and the given conditions.

## Q5: What are some real-world applications of mod problem?

Mod problem has many real-world applications, including computer programming, cryptography, and data encryption. It is also used in fields such as engineering, finance, and physics to solve various problems involving remainders and periodic patterns.

Replies
1
Views
5K
Replies
11
Views
1K
Replies
4
Views
1K
Replies
16
Views
1K
Replies
16
Views
2K
Replies
4
Views
2K
Replies
5
Views
2K
Replies
6
Views
1K
Replies
6
Views
1K
Replies
1
Views
2K