论坛 › 难题征解 › 不同余数的个数

fungarwai 发表于 2014-9-6 18:03:01

不同余数的个数

http://kuing.orzweb.net/viewthread.php?tid=2877&extra=page%3D5

求$1^{2013},2^{2013},......,2013^{2013}$除以$2013$,得到的不同余数的个数。

cn8888 发表于 2014-9-9 08:55:56

693

cn8888 发表于 2014-9-9 09:02:48

Clear["Global`*"];(*Clear all variables*)
a=Table,{k,1,2013}];
Length@Union@a

fungarwai 发表于 2014-9-9 09:52:36

奇怪了，考虑$2013=3\times 11\times 61$的话，61的余数少了16个
不是应该$3\times 11\times 45=1485$吗？

fungarwai 发表于 2014-9-9 10:21:28

对不起，我让Matlab直接算mod(x^33,61)所以错了
$3\times 11\times 21=693$

fungarwai 发表于 2014-9-9 10:52:23

for x=1:2013
        a(x)=1;
        for n=1:2013
                a(x)=mod(x*a(x),2013);
        end
        b(a(x)+1)=1;
end
sum(b)

除了这样做以外还有什么方法可以让matlab算对吗？

cn8888 发表于 2014-9-9 10:53:21

\[\begin{gathered}
:2013 = 3 \times 11 \times 61 \hfill \\
{x^{2013}} \equiv {x^1}(\bmod 3)\frac{{3 - 1}}{{(3 - 1,1)}} + 1 = 3 \hfill \\
{x^{2013}} \equiv {x^3}(\bmod 11)\frac{{11 - 1}}{{(11 - 1,3)}} + 1 = 11 \hfill \\
{x^{2013}} \equiv {x^{33}}(\bmod 61)\frac{{61 - 1}}{{(61 - 1,33)}} + 1 = 21 \hfill \\
3*11*21 = 693 \hfill \\
\end{gathered} \]

fungarwai 发表于 2014-9-9 11:26:03

本帖最后由 fungarwai 于 2014-9-9 11:28 编辑

cn8888 发表于 2014-9-9 10:53
\[\begin{gathered}
:2013 = 3 \times 11 \times 61 \hfill \\
{x^{2013}} \equiv {x^1}(\bmod 3)\fr ...

厉害！似乎这个公式对$(modp)$都有效，但$(modp^m)$又如何处理呢？再凑凑看

\(\displaystyle x^2(mod4):2,\frac{4-1}{(4-1,2)}+1=4\)

\(\displaystyle x^3(mod4):3,\frac{4-1}{(4-1,3)}+1=2\)

\(\displaystyle x^4(mod4):2,\frac{4-1}{(4-1,4)}+1=4\)

cn8888 发表于 2014-9-9 11:38:14

\[{x^m}(\bmod {p^k}),\frac{{\varphi ({p^k})}}{{\gcd (\varphi ({p^k}),m)}} = \frac{{{p^{k - 1}}(p - 1)}}{{\gcd ({p^{k - 1}}(p - 1),m)}}\]

fungarwai 发表于 2014-9-9 12:54:54

本帖最后由 fungarwai 于 2014-9-9 13:06 编辑

\(\displaystyle \frac{\varphi(3^k)}{(\varphi(3^k),2)}=3^{k-1}\)

\(x^2(mod3^1):1+1=2\)
\(x^2(mod3^2):3+1=4\)
\(x^2(mod3^3):3^2+2=11\)
\(x^2(mod3^4):3^3+4=31\)
\(x^2(mod3^5):3^4+11=92\)
\(x^2(mod3^6):3^5+31=274\)
\(x^2(mod3^7):3^6+92=821\)

\(\displaystyle \frac{\varphi(5^k)}{(\varphi(5^k),2)}=5^{k-1}2\)

\(x^2(mod5^1):2+1=3\)
\(x^2(mod5^2):10+1=11\)
\(x^2(mod5^3):50+3=53\)
\(x^2(mod5^4):250+11=261\)
\(x^2(mod5^5):1250+53=1303\)
\(x^2(mod5^6):6250+261=6511\)
\(x^2(mod5^7):31250+1303=32553\)

\(\displaystyle \frac{\varphi(5^k)}{(\varphi(5^k),3)}=5^{k-1}4\)

\(x^3(mod5^1):4+1=5\)
\(x^3(mod5^2):20+1=21\)
\(x^3(mod5^3):100+1=101\)
\(x^3(mod5^4):500+5=505\)
\(x^3(mod5^5):2500+21=2521\)
\(x^3(mod5^6):12500+101=12601\)
\(x^3(mod5^7):62500+505=63005\)

查看完整版本: 不同余数的个数