d能帮助爱丽丝解密信息，其原因可以归结为模算术（modular arithmetic）的特性，以及当de除以 k=φ(n)时余1这一事实。爱丽丝计算(me)d=mde模n。现在de具有1＋kr的形式，这里r是某个整数。正如之前解释的那样，mk除以n余1，这通常被称为欧拉定理（Euler's Theorem），而这对于(mk)r=mkr也是对的。因此，m1＋kr=m×mkr，它除以n余m。（详细的验证需要一点代数运算，不过结果的确是这样的。）通过这个方法，爱丽丝得到了鲍勃的信息——m。
顺便指出，我们在证明素因数分解唯一性的时候缺少了一环，欧几里得算法恰好提供了这缺失的环节。因为它使得我们能够验证欧几里得性质，即如果素数p是乘积ab的一个因数，比方说ab=pc，那么p是a和b之中至少一个的因数。如果p不是a的一个因数，那么由于p是素数，a和p的最大公因数是1。应用欧几里得算法于a和p这对数，并将其反转，我们可以找到整数r和s，使得ra＋sp=1。这已经足够证明p是b的一个因数了。由于ab=pc，我们有：
