What are the possible solutions for x in the congruence equation?

[mattmns]

Question 1.

6x + 3 \equiv 1 mod 10

I added 8 \equiv 8 mod 10
and got
6x + 11\equiv 9 mod 10
then subtracted 11 \equiv 1 mod 10
and have

6x \equiv 8 mod 10, but am stuck here. Any ideas?




Question 2.

x^2 \equiv 1 mod 21

This one I am lost on. Maybe subtract 1, and then use (x+1)(x-1), but I am not feeling that way either. Thoughts? Danke!

 

[amcavoy]

Question 1.

6x + 3 \equiv 1 mod 10

I added 8 \equiv 8 mod 10
and got
6x + 11\equiv 9 mod 10
then subtracted 11 \equiv 1 mod 10
and have

6x \equiv 8 mod 10, but am stuck here. Any ideas?




Question 2.

x^2 \equiv 1 mod 21

This one I am lost on. Maybe subtract 1, and then use (x+1)(x-1), but I am not feeling that way either. Thoughts? Danke!

I don't know too much about number theory, but I think you are correct in your assumption on the second question. If you did that, it would mean that either (x+1) or (x-1) is some multiple of 21. From there you can solve.

 

[shmoe]

If you did that, it would mean that either (x+1) or (x-1) is some multiple of 21.

You could have x+1 a multiple of 3 and x-1 a multiple of 7, so you can't just look at multiples of 21 (the integers modulo 21 is not a field, it has zero divisors).

You do know x^2-1 is a multple of 3 and 7, so consider the equation mod 3 and 7 seperately (here your factorization will work). You'll have a couple possibilities for x mod 3 and for x mod 7. Combine to get the possibilities for x mod 21.

For the first question, you can do something similar and consider it mod 2 and mod 5.

 

[mattmns]

Ok that sounds interesting, but I need to see an example.

Here is what I tried from the first problem:

6x \equiv 8 mod 10

So, what I got from what you said, I may have misinterpreted:

6x \equiv 3 mod 5
6x \equiv 0 mod 2

Then for the first one subtract 5x \equiv 0 mod 5 and get x \equiv 3 mod 5

Now for the second one.

6x \equiv 0 mod 2
So because 2 is a prime I used euclid's lemma and got

2|6 or 2|x

Therefore x \equiv 0 mod 2

So I then combine those to get solutions for 6x + 3 \equiv 1 mod 10

to be the following.

x \equiv 3 mod 5
x \equiv 0 mod 2

Did I do that correctly?

 

[shmoe]

Now for the second one.

6x \equiv 0 mod 2
So because 2 is a prime I used euclid's lemma and got

2|6 or 2|x

Hang on here, you want to know for what values of x does 2 divide 6x. In any case, knowing that

x\equiv 3\mod\ 5

what are the possibilities for x mod 10?


for the other one, first solve x^2-1\equiv 0\mod\ 3 and x^2-1\equiv 0\mod\ 7 either by factoring as you wanted to (why will this work here?) or by trying all the possibilities for x. Then we can get into combining the answers (a little more to combining them here. It's not necessary that you know it, but you'll essentially be using the Chinese Remainder theorem).

 

[mattmns]

The possibilities would be x \equiv 3 mod 10 and x \equiv 8 mod 10 right?

One quick question. For all values of x, 2 divides 6x correct? Because 2|6x => 1|3x ? So we then combine the similar possibilities? And because x can be anything according to the second equation, we just use the possibilities for the first equation which are x \equiv 3 mod 10 and x \equiv 8 mod 10

Is that the way it is supposed to be done?

 

[neurocomp2003]

dude are you actually using a number theory textbook? or did those Qs just pop into your head? Cuz i can't see how a textbook doesn't teach you how to solve those quesitons.

the x^2 is a square modulo question(or Quadratic residue).

THe first question. You will be applying the linear congruene theorem

ax=c(modm), au+mv=g: a, your scalar on x, m is the factor, g is your gcd.
u is your solution and v is a quantity for other number theory apps.

Now the condition is if g divides c there are g incongruent solutions.
and to solve this you reorder it as: au+mv=g
and solve for u and v...u is your solution. You do this solving technique through the
GCD extended. And if you don't know what that is...i don't see how your taking number theory.

 

[mattmns]

It is an abstract algebra book that is quickly skimming over number theory with no examples at all lol. And I have no idea what you are saying, I will ask my prof tomorrow. I personally do not think these questions are that important to abstract algebra, I could always be wrong though. Thanks for the help all who responded.

 

[neurocomp2003]

oh lol my bad yeah some number theory is always covered in abstract algebra...
go to mathworld.com and search for the number theory sectoin and look up
linear congruence theorm (Q1) and (Q2)square modulus. HOpefully mathworld will outline the methods of solving.

 

[shmoe]

The possibilities would be x \equiv 3 mod 10 and x \equiv 8 mod 10 right?

One quick question. For all values of x, 2 divides 6x correct? Because 2|6x => 1|3x ? So we then combine the similar possibilities? And because x can be anything according to the second equation, we just use the possibilities for the first equation which are x \equiv 3 mod 10 and x \equiv 8 mod 10

Is that the way it is supposed to be done?

Yes, this is fine.

These are important to abstract algebra, it's helping to take the "abstract" out by giving you examples to pick from later on of groups, rings, fields, that aren't your usual integers, rationals, etc. If you later take a number theory course you'll meet many results that are just theorems in abstract algebra applied to special cases in modular arithmetic, so it's nice to see some kind of connection off the bat.

 

[Mithal]

I think it could be solved this way

1-)

6 x +3 = 1 mod 10

6 x =-2 mod 10

3 x = -1 mod 5

3 x = 4 mod 5

or

3 x - 5 y =4

x = 3 , y =1

or

x =3 mod 5

2-)

x^2 = 1 mod 21

x must be in the same form as x^2

x=a +21 t

after substituting , we find

a^2 = 1 mod 21

We check for a= 1,2,3,...21 to satisfy the above ,we find

a= 1 ,8,13,20

x=1 mod 21
x=8 mod 21
x=13 mod 21
x=20 mod 21

 

[HallsofIvy]

"Checking" for x= 1, 2, 3, ..., 10, while tedious, is exactly what I would do.

However, does reducing from "x²= 1 mod 21" to "a²= 1 mod 21" actually help?

Notice that you don't really have to go all the way to 20. After you have found that x= 1 and 8 are the only solutions less than or equal to 10, you also know that x= -1 mod 21= 20 mod 21 and x= -8 mod 21= 13 mod 21 are the only other solutions.