1

At the 6:50 min mark of this video: https://courses.edx.org/courses/HarvardX/CS50x3/2015/courseware/c0986764d695405f9d995f43b7c10676/5194906ad75c4edb9ecd401df372b8f3/

here's a screen shot, too: http://imgur.com/XuU8a23 [2]

Isn't 1 mod 924 = 1, because the remainder in 1/924 is 1

In the video he declares e = 5

and then says de = 1 mod m

and quickly says that number is 185.

But why? shouldn't de = 1, in order to satisfy de = 1 mod m? Instead de = 925 or 5 * 185.

I went out and did the set on Khan academy for modulo arithmetic just to brush up my memory, but even with that I still don't get it. I get what x mod y means, I've been using it in the code for my problem sets, but what I don't get is why 1 mod anything is not 1.

I'm sure I'm missing something here.

PS: I'm aware he explains the process more around the 15 min mark, but what I never see explained is why if 1 mod 924 = 1, why doesn't d*e have to equal 1, if it is meant to "satisfy the equation"

1
  • EDIT: I have the answer. 925 and 1 both satisfy 1 mod 924. So d * e must equal 925, which is how the values make sense. – TryingToLearn May 11 '15 at 12:10
1
de = 1 (mod m)

where e is equal to 5 and m is equal to 924 means

(5 * d) % 924 = 1

Thomas later in the video used the extended Euclidean algorithm to find a value of d that would satisfy the equation above. However, in this specific example, you could find a value of d that would satisfy the equation easily since 925 % 924 = 1 and we're lucky that e is equal to 5 and that divides the 925, so d is 925 / 5 which is equal to 185.

0

It's de = 1 (mod m) not de = 1 mod m

(mod m) is giving you the size of the wrap around. For example, (mod 60) is same size as a 60 minute clock.

In that specific case 1 (mod 60) can be any of the following sequence 1, 61, 121, 181, ...

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .