Need help to understand Mod Arithmetic question.

NotGoodAtAll

New member
Joined
Oct 30, 2019
Messages
9
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!
 
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!
 
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
 
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.
 
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.
 
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.
 
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.
 
Last edited by a moderator:
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.
 
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.
 
Top