Homework Help: Two Congruence questions

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.

 

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.

 

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

[tex]x\equiv 3\mod\ 5[/tex]

what are the possibilities for x mod 10?


for the other one, first solve [tex]x^2-1\equiv 0\mod\ 3[/tex] and [tex]x^2-1\equiv 0\mod\ 7[/tex] 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).

 

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.

 

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.

 

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.

 

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

 

"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.