Modular Arithmatic

RolandIRL

how do you get the inverse of a number in modular arithmatic?
eg find the inverse of 6 in Z11.

A woman has between 100 and 200 eggs in the basket. Counting in threes there is 1 egg leftover, counting in fives there are 2 eggs leftover and counting in sevens there are 3 eggs leftover. How many eggs are in the basket?
i know the answer by eliminating numbers until i was left with the correct answer. but how would you do this mathematically by modular arithmatic?


i just want to check the answer to this.
x^2 + 1 (congruent symbol) 0 mod 65
x = +8 or x =57

Pherekydes

whiteman19 wrote: »

how do you get the inverse of a number in modular arithmatic?
eg find the inverse of 6 in Z11.

A woman has between 100 and 200 eggs in the basket. Counting in threes there is 1 egg leftover, counting in fives there are 2 eggs leftover and counting in sevens there are 3 eggs leftover. How many eggs are in the basket?
i know the answer by eliminating numbers until i was left with the correct answer. but how would you do this mathematically by modular arithmatic?


i just want to check the answer to this.
x^2 + 1 (congruent symbol) 0 mod 65
x = +8 or x =57

The inverse of a number is a number such that when the number and its inverse are multiplied by each other you get 1. This works in modular arithmetic, too.

Counting in threes: x is congruent to 1 mod 3

The last part is partially correct. The are four solutions because 65 is...?

LeixlipRed

To expand on previous post you should note that the inverse of a (mod n) exists if and only if the gcd of a and n is 1. Which in this case is true and you can find the inverse of a using Euclid's algorithm which you've seen before I'm sure.

Second one can be solved by using Chinese Remainder Theorem but there is an easier way using the a definition from modular arithmetic, mainly that if (= stands for congruent here) a=b (mod n) that means that a= kn + b.

RolandIRL

i'm not following the extra solutions to x^2 + 1 congruent to 0 mod 65. is it that there's a general solution to the question?

for the eggs, i've written the congruences as x = {3,5,7}k + {1,2,3} 3 correspondong to 1 etc..
i'm not sure where to go from here.

RolandIRL

for x^2 + 1 congruent to 0 mod 65, would plus or minus i=(-1)^1/2 be the extra two solutions or are the solutions limited to R or Z?

LeixlipRed

The solutions are limited to Z!

Ok, for the second one, you have x=1 (mod 3) or x=3k + 1. So fill in this value for x in your second congruence (x=2 (mod 5)) and you have 3k + 1=2 (mod 5) and solve for k. Any idea where I'm going with that?