Need help to understand Mod Arithmetic question.

[NotGoodAtAll]

Hi,

Looking at a math question that has thrown me. I can't work out what I'm being asked for, though I have blasted through a lot of modular arithemetic questions in the last 4 hours so it might just be me.

Choose the two options giving a modulus n for which 45^-1 exists modulo n :

18
28
50
69
94

I am having a complete nightmare. Anyone who could help here would be amazing!

 

[Cubist]

In modular arithmetic there seems to be a term "existence" which means there exists an integer denoted a^–1 such that a*a^–1 ≡ 1 (mod n) if and only if a is coprime with n. (I just found this out myself.)

If numbers are coprime then their gcd is 1. gcd(45,18)=9 so that isn't one of the numbers. I'll leave it to you to try the rest!

 

[Steven G]

You want to find n such that 45x = 1 mod(n) where x is an integer

 

[NotGoodAtAll]

Thanks both.

Hilariously, I hit 9 in my first stab at this and thought I had made an error. Appears not, simply that I did not continue with the logic.

Many thanks

 

[Steven G]

In modular arithmetic there seems to be a term "existence" which means there exists an integer denoted a^–1 such that a*a^–1 ≡ 1 (mod n) if and only if a is coprime with n. (I just found this out myself.)

If numbers are coprime then their gcd is 1. gcd(45,18)=9 so that isn't one of the numbers. I'll leave it to you to try the rest!

I knew this fact but wanted the student to get the answer without using it. I felt that would help the student understand what inverses were. For the record, for some reason I did not see your post when I added mine.

 

[NotGoodAtAll]

Hi,

I've been playing with modular arithmetic for a few weeks, trying to get a grasp of cryptography along with the mathematical theories that surround the algorithms.

Rest assured, both sets of inputs from yourselves set a chain reaction of memory and thought off, and helped me come to the conclusion. Please accept my greatest thanks for this, I had hit a mental block and needed a push.

 

[Cubist]

I knew this fact but wanted the student to get the answer without using it. I felt that would help the student understand what inverses were. For the record, for some reason I did not see your post when I added mine.

That was one of my first posts, so it didn't become public until a moderator approved it. I guess I answered, and then you answered (before my post was approved/ visible). No harm done.

Regarding detail, I'll aim to give subtler hints when trying to help.

 

[Kimashik]

You can seek help if you need to solve the problem with your task. There you'll find assistants who'll be able to help. I was getting ready for my final exams with their help and passed them with no sweat.

 

[Steven G]

You can seek help if you need to solve the problem with your task. There you'll find assistants who'll be able to help. I was getting ready for my final exams with their help and passed them with no sweat.

Where is there?
I doubt that you mean here, as this is your first post.

 

[HallsofIvy]

Jomo, Since Kimashik's post was "edited by a moderator", I suspect the word "There" was originally a link to a pay site.

NotGoodAtAll, 45= 3(3)(9). You need to know that "a" has an inverse, "modulo n" if and only if n has no factors in common with a.

 

[NotGoodAtAll]

Thanks again, I managed to get to grips with it to some extent. Though I'm working on an a slightly more interesting and challenging Modular arithmetic question that led on from this one. Thankfully, the gentle push that I was given by the wonderfully intelligent people of this forum proved quite helpful in the previous question.

 

[HallsofIvy]

Oops. I just noticed. No, 45 is NOT equal to 3(3)(9). I meant to write 3(3)(5).