Question

Find a positive inverse for 3 modulo 40. That is find a positive integer s such that 3s=1(mod 40)

Answer 1

27 works, I guess

Answer 2

haha that is teh right answer but how did u get that?

Answer 3

I don't know, guesswork, which I guess, is not the right way to go about it. Perhaps you would enlighten me?

Answer 4

u need to use linear combination. but can u explain me ur logic?

Answer 5

yeah, I just used trial and error...
40.... 40+1 divisible by 3? no
80.....80+1 divisible by 3? yes, it must be 81/3 then :)

Answer 6

And I don't know what linear combination is :P

Answer 7

hahah ok thanks :)

Answer 8

programmatically i found 27 too

Answer 9

ya its the answer but like i dont know how to solve ut. like they have this weird method

Answer 10

3*s - 1 must be greater than 40
which means s>14

Answer 11

3s-1 must have zero at end therefore s must be 17, 27, 37, 47, ..

Answer 12

okkkk i see u just use logic

Answer 13

i used computer to find it first ..

Answer 14

on the other hand, we have
3s - 1 should be divisible by 4 too

Answer 15

or,
3s = 1mod(4)
3s = 1mod(10)

Answer 16

from,
3s = 1mod(4)
we have
s = 3,7,11,15,19,23,27,31, ...


hence, the first intersection occurs at s = 27
so this is the answer

Answer 17

ohhh i seee i like this method

Answer 18

well, i'm still not pretty much convinced if you can use this method ... algebra should be more fundamental than this ... i guess

Answer 19

THANKS :DDDDDDDDD

Answer 20

yw .. if i find any better, i'll update

Answer 21

i got this
http://math.stackexchange.com/questions/67969/solve-100x-23y-19/68021#68021

Answer 22

you want to solve \(3x\equiv 1( \text{mod }40)\) one way to do this is use the euclidean algorithm

Answer 23

i'm interested .. please go on

Answer 24

ya that is method i need to use

Answer 25

in this case you are lucky, because it only takes one step

Answer 26

you get \(40=13\times 3+1\)

Answer 27

right

Answer 28

this tell you \(1=1\times 40-13\times 3\) and so the inverse of 3 is -13

Answer 29

which of course is the same mod 40 as 27

Answer 30

didnt follow the last step

Answer 31

you are lucky in this case that you get it right away. if you wanted compute the inverse of 7 mod 40 it might take more steps
was the answer clear?

Answer 32

ok i thought maybe not

Answer 33

liek abt the inverse

Answer 34

you want \(3\times x\equiv 1(40)\) which by definition means 40 divides \(3x-1\)

Answer 35

which in turn means \(3x-1=40k\) for some \(k\) or \(1=40j+3x\)

Answer 36

ok got that part

Answer 37

\(j\) and \(x\) are called the "bezout coeffients" so that is what you are looking for

Answer 38

by the euclidean algorithm, divide 40 by 3 as needed until you get a remainder of 1. in this case it only takes one step, so this one is very easy. so we have
\[40=13\times 3+1\] solving for 1 gives
\[1=40-13\times 3\] so the coefficient for 3 is -13

Answer 39

that means the inverse of 3 is -13
but generally since you are working mod 40 your universe is positive integers between 0 and 39, so you would say -13 = 40-13 = 27 and that is your inverse

Answer 40

ohhhhh i get it. Like my book never explained what inverse was

Answer 41

lol
what book?

Answer 42

text book

Answer 43

YAY that was awesome SAT :D

Answer 44

well ... thanks for new method ...

Answer 45

we can also do this the donkey way, which might be easier and make more sense

Answer 46

start with \(3x\equiv 1(40)\) and you want to divide by 3, but you cannot
so keep adding 40 until you can

Answer 47

hahah i never heard of teh donkey way lol

Answer 48

\(3x\equiv 1(40)\)
\[3x\equiv 41(40)\] still can't divide by 3
\[3x\equiv 81(40)\] ahh now we can divide!
\[3x\equiv 81(40)\]
\[x\equiv 27(40)\]

Answer 49

this way is in fact rather easy, especially if you have small numbers and can get it right away

Answer 50

in fact if i was going to do this on an exam, this is probably the method i would use

Answer 51

OK thanks sattelite. Sorry os is freezing my comp

Answer 52

yw, hope it is clear