48=4×11+4
11=2×4+3
4=1×3+1
confirming that the hcfofk and e is indeed 1. Reversing the algorithm we obtain:
1=4-3=4-(11-2×4)=3×4-11=3(48-4×11)-11
=3×48-13×11.
This gives an initial value ofd=-13 as the solution to the requirement that 11d leaves remainder 1 upon division by 48, so in order to get a positive value ofd in the required range we add 48to this number to get d=48-13=35.
The reason why dworks for Alice is all down to modular arithmetic and the fact that de leaves a remainder of1 when divided by k=φ(n). Alice calculates(me)d=mde modulo n. Now de has the form 1+kr for some integer r. As explained before, mkleaves a remainder of1 when divided by n(this is often known as Euler’s Theorem)and so the same is true of(mk)r=mkr. Hence m1+kr=m×mkr leaves the remainder mwhen divided by n.(Detailed verification ofthis requires a little algebra, but that is what happens.)In this way, Alice retrieves Bob’s message, m.