软件开发协会的挑战书

在RSA密码体系中, 欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 $ax\equiv 1\pmod n$ 这种方程。整个解的过程是这样的，我们用一个例子来说明。

当 a = 1001 ，n = 3837 时，方程为 x * 1001 ≡ 1 (mod 3837)
我们有
3837 = 3 * 1001 + 834
1001 = 1 * 834 + 167
834 = 4 * 167 + 166
167 = 1 * 166 + 1

所以

1 = 167 + (–1) * 166
= 167 - (834 - 4 * 167)
= -1 * 834 + 5 * 167
= 5 *(1001 - 834) – 834
= 5 * 1001 + (-6) * 834
= 5 * 1001 - 6 * (3837 -3 * 1001)
= -6 * 3837 + 23 * 1001

然后对等式两端同时模 3837 得

23 * 1001 ≡ 1 (mod 3837)

于是 x = 23

现在给出 a=1699 和 n=1110，你能解出这个方程吗？

现有一串十进制数字 94171??1? 为QQ群号(第6、7、9位未知)其中，第6位和第7位是x的后两位数字

求得x后补全得群号前8位数字，该数字转16进制后，16进制数的最后一位即为群号的第9位数字

解出群号进入群聊，且能较清晰地描述解题过程即视为挑战成功。前 5 名将获得软件开发协会纪念礼品一份，第一名将额外获得蓝牙耳机一副。

本活动仅限于本校学生，老师请勿参赛。（doge）