Introductory Linear Algebra - Modular Arithmetic

sunmaz94
Messages
42
Reaction score
0

Homework Statement



a) For which values of a does ax = 1 have a solution in Z5?
b) For which values of a does ax = 1 have a solution in Z6?
c) For which values of a and m does ax = 1 have a solution in Zm?

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.
 
Physics news on Phys.org
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.
 
Last edited by a moderator:
Have you seen the following:

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

If not, try to prove it. To prove it, you most likely need Bezout's theorem...
 
Thanks.
 
HallsofIvy said:
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!
 
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?
 
Last edited:
We take both a and x to be in \mathbb{Z}. This is the usual convention to deal with modular arithmetic.
 
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?
 
Last edited:
HallsofIvy said:
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.

.
 
  • #10
crni said:
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.
 
  • #11
HallsofIvy said:
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.
 

Similar threads

Back
Top