7
17
2014

### 一个xx的数论笔记

$$d|a, d|b$$

$$d|y$$

$$d|a~mod~b$$

$$gcd(a,b)=gcd(b,a~mod~b)~~~~(1)$$

$$bx+(a~mod~b)y=gcd(b,a~mod~b)$$

$$bx'+(a~mod~b)y'=ax+by$$

$$bx'+(a-\lfloor\frac{a}{b}\rfloor b)y'=ax+by$$

$$b(x'-\lfloor\frac{a}{b}\rfloor y')+ay'=by+ax$$

$$y=x'-\lfloor\frac{a}{b}\rfloor y',x=y'$$

$$\frac{B}{A}>\frac{y}{x}>\frac{D}{C}$$

$$\frac{B-\lfloor\frac{B}{A}\rfloor A}{A}>\frac{y-\lfloor\frac{B}{A}\rfloor x}{x}>\frac{D-\lfloor\frac{B}{A}\rfloor C}{C}$$

$$x=y',y=x'+\lfloor\frac{B}{A}\rfloor x~~~~(2)$$

$$return~~~x'=1,y'=1$$

$$A^{xS+y}\equiv B(~mod~C)$$

$$A^{xS}\equiv \frac{B}{A^y}(~mod~C)$$

$$D=kC+B$$

$$\frac{D}{t}=k\frac{C}{t}+\frac{B}{t}$$

$$\frac{D}{t}\equiv \frac{B}{t}(~mod~\frac{C}{t})$$

$$t=gcd(A,C) [tex]if~t\nmid B,~No~Solution$$

$$E=gcd(A,C)gcd(A,C_1)...gcd(A,C_{s-1})$$

$$A^{a-s}\frac{A^s}{E}\equiv \frac{B}{E}(~mod~\frac{C}{E})$$

$$B'=\frac{B}{E}$$

$$A^{a-s}\equiv \frac{B'E}{A^s}(~mod~\frac{C}{E})$$

$$F+s~$$是一个可行解

$$x=\prod_{i=1}^{k_x}{p_i^{q_i}}$$,我们定义这样两个函数：

$$e(x)=\begin{cases}0~~~~~~~~~~x>1\\1~~~~~~~~~~x=1}\end{cases}~~~~~~~~~~~~~~~~~~~(1)$$

$$\mu(x)=\begin{cases}1~~~~~~~~~~x=1\\(-1)^{k_x}~~~\forall~q_i,~q_i<2\\0~~~~~~~~~~\exists~q_i,~q_i>=2}\end{cases}~~~~~~~~(2)$$

$$\sum_{d|x}{\mu(d)}=\sum_{i=0}^{k_x}{\binom{k_x}{i}(-1)^i$$

$$\sum_{d|x}{\mu(d)}=(1-1)^{k_x}$$

$$\sum_{i=1}^{n}{\sum_{j=1}^{m}{f(gcd(i,j))}}$$

$$=\sum_{d_1=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{d_1} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{d_1} \rfloor}{f(d_1)e(gcd(i,j))}}}$$

$$=\sum_{d_1=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{d_1} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{d_1} \rfloor}{f(d_1)\sum_{d_2|gcd(i,j)}{\mu(d_2)}}}}$$

$$=\sum_{d_1=1}^{min(n,m)}{\sum_{d_2=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{d_1 d_2} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{d_1 d_2} \rfloor}{f(d_1)\mu(d_2)}$$

$$=\sum_{c=1}^{min(n,m)}{\sum_{i=1}^{\lfloor \frac{n}{c} \rfloor}{\sum_{j=1}^{\lfloor \frac{m}{c} \rfloor}{\sum_{d|c}{f(d)\mu(\frac{c}{d})}}}}$$

$$=\sum_{c=1}^{min(n,m)}{\sum_{d|c}{f(d)\mu(\frac{c}{d})}\lfloor \frac{n}{c} \rfloor\lfloor \frac{m}{c} \rfloor}$$

$$g(c)=\sum_{d|c}{f(d)\mu(\frac{c}{d})}$$

$$=\sum_{c=1}^{min(n,m)}{g(c)\lfloor \frac{n}{c} \rfloor\lfloor \frac{m}{c} \rfloor}~~~~~~~~ (1)$$

$$\mu(x)$$是积性函数，若$$f(x)$$同样是积性函数那么$$g(x)$$也是积性函数，这是一个狄利克雷卷积。

Category: Number Theory | Tags: Number Theory | Read Count: 3075
AAA said:
Sat, 09 Apr 2022 18:46:40 +0800

Thank you for taking the time to publish this information very useful! 온라인카지노