最近遇到一个根据欧拉数求解原数的例子，即已知Euler(Q)的值，求解Q，另已知Q=q^2，且q为质数。

欧拉函数性质

  1. 欧拉函数为积性函数。（对于数论函数 f(n) 不恒等于0，当 (m,n) = 1 时，满足 f(mn) = f(m)f(n) ，则称 f(n) 为积性函数） φ(mn) = φ(m)φ(n)，(m,n) = 1
  2. 若 (m,n) = d，则φ(mn) = dφ(m)φ(n)/φ(d)
  3. 若m、n满足m|n，则φ(mn) = mφ(n)
  4. 若m、n满足m|n，则φ(m)|φ(n)
  5. 对于质数p，其欧拉函数公式为φ(p) = p-1
  6. 对于质数p，p^k的欧拉函数公式为φ(pk) = (p-1) · p^（k-1）
  7. 小于等于n且整除n的所有正整数的欧拉函数值之和等于n，即n = Σd|nφ(d)
  8. 欧拉定理：若(a,m) = 1，则 aφ(m) ≡ 1 (mod m)。
  9. 扩展欧拉定理
  • ax ≡ ax mod φ(m) (mod m)，(a,m) = 1
  • 或ax ≡ ax  (mod m)，(a,m) ≠ 1且x < φ(m)
  • 或 ax ≡ ax mod φ(m) + φ(m) (mod m)，(a,m) ≠ 1且x ≥ φ(m)

求解一个数的欧拉函数

1
2
3
4
5
6
7
import gmpy2
def Euler(x):
    res=0
    for i in range(1,x):
        if gmpy2.gcd(i,x)==1:
            res+=1
    return res

编写求解脚本

根据6可知，当k=2时，Euler(q x q)=q x (q-1)；当已知Euler(Q)时，求解q就不难了。

1
2
3
4
Euler(Q)+0.25=(q-0.5)^2;
100Euler(Q)+25=(10q-5)^2;
10q=sqrt(100Euler(Q)+25)+5
q=(sqrt(100Euler(Q)+25)+5)/10

根据以上求解直接写出求解的python脚本

法一

考虑精度问题，没有使用math.sqrt，直接使用二分法求解平方根（即使输入不对，也会给出一个相近的结果）；（无需安装第三方库，只能求解Euler(q^2)类型）

1
2
3
4
5
6
7
8
9
10
11
12
13
x = int(input('input Euler(q*q):'))
x=100*x+25
low, high, ans = 0, x, -1
while low <= high:
    mid = (low + high) // 2
    if mid * mid <= x:
        ans = mid
        low = mid + 1
    else:
        high = mid - 1
ans+=5
q=ans//10
print('q is',q)

法二

直接利用sympy库进行解方程；pip install sympy；（直接求解）
利用sympy求解方程时，需保证方程右边的结果为0，即任意方程E(x)=a，需变换成E(x)-a=0，写入sympy.solve中为方程左式即可。（可求解任意k>=2值类型）

1
2
3
4
5
6
7
8
9
10
11
12
13
import sympy
q=sympy.Symbol('q')
print('q**k')
k = input('input k(default 2):').strip()
if not k.isdigit():
	k='2'
k = str(int(k)-1)
x = input('input Euler(q*q):')
ans=sympy.solve(x+'-(q-1)*q**'+k,q)
print()
for an in ans:
	print('q is',an,'\n')
print('end')