Introductory Linear Algebra - Modular Arithmetic

[sunmaz94]

Homework Statement

a) For which values of a does ax = 1 have a solution in Z₅?
b) For which values of a does ax = 1 have a solution in Z₆?
c) For which values of a and m does ax = 1 have a solution in Z_m?

Homework Equations

None.

The Attempt at a Solution

Answers:

a) All a ≠ 0
b) a = 1, 5
c) a and m have no common factors other than 1 [i.e., the gcd of a and m is 1].Please explain, in detail, why these are the answers and how one arrives at them. I honestly haven't the faintest clue. Thanks.

 

[HallsofIvy]

a) It's not that hard to just do the calculations. if a= 1, then ax= x= 1 has the obvious solution. If a= 2, it is easy to see that ax= 2x= 1 has the solution x= 3 because 2(3)= 6 = 1 mod 5. If a= 3, it is just as easyto see that ax= 3x= 1 has the solution x= 2 for the same reason. If a= 4, ax= 4x= 1 has the solution x= 4 because 4(4)= 16= 1 mod 5.

b) If a= 1, ax= x= 1 has the obvious solution. If a= 2, 2x= 1 has NO solution because 2x is always even and will never be 1 more than a multiple of 6. If a= 3, 3x= 1 has NO solution because 3x is alway a multiple of 3 and will never be 1 more than a multiple of 6. If a= 4, 4x is again even. If a= 5, 5x= 1 when x= 5, 5(5)= 25= 1 mod 6.

c) Put those ideas together. If m and a have a common factor n> 1, then any multiple of a, ax, will be a multiple of n and so cannot be 1 more than m which is also a mutiple of n.

 

[micromass]

Have you seen the following:

a has a multiplicative inverse in [tex]\mathbb{Z}_n[/tex] if and only if gcd(a,n)=1.

If not, try to prove it. To prove it, you most likely need Bezout's theorem...

 

[sunmaz94]

Thanks.

 

[sunmaz94]

a) It's not that hard to just do the calculations. if a= 1, then ax= x= 1 has the obvious solution. If a= 2, it is easy to see that ax= 2x= 1 has the solution x= 3 because 2(3= 6 = 1 mod 5. If a= 3, it is just as easyto see that ax= 3x= 1 has the solution x= 2 for the same reason. If a= 4, ax= 4x= 1 has the solution x= 4 because 4(4)= 16= 1 mod 5.

b) If a= 1, ax= x= 1 has the obvious solution. If a= 2, 2x= 1 has NO solution because 2x is always even and will never be 1 more than a multiple of 6. If a= 3, 3x= 1 has NO solution because 3x is alway a multiple of 3 and will never be 1 more than a multiple of 6. If a= 4, 4x is again even. If a= 5, 5x= 1 when x= 5, 5(5)= 25= 1 mod 6.

c) Put those ideas together. If m and a have a common factor n> 1, then any multiple of a, ax, will be a multiple of n and so cannot be 1 more than m which is also a mutiple of n.

Great. Thank you very much!

 

[Tolstoy]

On a)

What if a is not an integer, as in a = 0.23?

Then x = 1/0.23 = 4.3478...

It can't be just 'all a in Z except 0', because it is valid for a=0.2, but it still doesn't seem to be valid for all real nubers, e.g. a=0.23.

Note the question mentions the solution must be in Z mod 5, it does not constrain the constant. Or does it?

 

[micromass]

We take both a and x to be in [itex]\mathbb{Z}[/itex]. This is the usual convention to deal with modular arithmetic.

 

[Tolstoy]

Thanks. I am new to somewhat serious maths. Is that true only when dealing with modular arithmetic or more generally too? If there are regularities in those seemingly arbitrary decisions, what are they?

 

[crni]

a) It's not that hard to just do the calculations. if a= 1, then ax= x= 1 has the obvious solution. If a= 2, it is easy to see that ax= 2x= 1 has the solution x= 3 because 2(3)= 6 = 1 mod 5. If a= 3, it is just as easyto see that ax= 3x= 1 has the solution x= 2 for the same reason. If a= 4, ax= 4x= 1 has the solution x= 4 because 4(4)= 16= 1 mod 5.

b) If a= 1, ax= x= 1 has the obvious solution. If a= 2, 2x= 1 has NO solution because 2x is always even and will never be 1 more than a multiple of 6. If a= 3, 3x= 1 has NO solution because 3x is alway a multiple of 3 and will never be 1 more than a multiple of 6. If a= 4, 4x is again even. If a= 5, 5x= 1 when x= 5, 5(5)= 25= 1 mod 6.

c) Put those ideas together. If m and a have a common factor n> 1, then any multiple of a, ax, will be a multiple of n and so cannot be 1 more than m which is also a mutiple of n.

Could the answer for b) a = 1, 5 also include 7, since 7(1)= 7= 1 mod 6.

.

 

[HallsofIvy]

Could the answer for b) a = 1, 5 also include 7, since 7(1)= 7= 1 mod 6.

.

And 13= 2(6)+1= 1 (mod 6), and -5= -1(6)+ 1= 1 (mod 6), and 19= 3(6)+ 1= 1 (mod 6), ... Where do you stop?

There are a couple of different ways of thinking about modular arithmetic. In introductory course, which this appears to be, we restrict the possible values for the numbers, "modulo n", to be 0 to n-1. A slightly more sophisticated way of looking at it is to say that two numbers are "equivalent", modulo n, if their difference is evenly divisible by n and look at "equivalence classes". Typically, we identify a equilence class by the smallest non-negative number in it as its "representative".

Here, using the first way, we only consider the numbers 0 to 5 so 7 would not be an answer. The second way 1 and 7 are in the same equivalence class so are not different answers. Either "1" or "7" would be a correct answer but the convention would be to give "1" as the smallest non-negative member of the set.

 

[crni]

And 13= 2(6)+1= 1 (mod 6), and -5= -1(6)+ 1= 1 (mod 6), and 19= 3(6)+ 1= 1 (mod 6), ... Where do you stop?

There are a couple of different ways of thinking about modular arithmetic. In introductory course, which this appears to be, we restrict the possible values for the numbers, "modulo n", to be 0 to n-1. A slightly more sophisticated way of looking at it is to say that two numbers are "equivalent", modulo n, if their difference is evenly divisible by n and look at "equivalence classes". Typically, we identify a equilence class by the smallest non-negative number in it as its "representative".

Here, using the first way, we only consider the numbers 0 to 5 so 7 would not be an answer. The second way 1 and 7 are in the same equivalence class so are not different answers. Either "1" or "7" would be a correct answer but the convention would be to give "1" as the smallest non-negative member of the set.

Yes, actually I was thinking 13, 19, etc. as well, but mentioned only 7. Thanks, this explanation makes the answer clear.