不同余数的个数

fungarwai

http://kuing.orzweb.net/viewthre ... &extra=page%3D5

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

cn8888

693

cn8888

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

复制代码

fungarwai

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

fungarwai

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

fungarwai

1. for x=1:2013
   
2.         a(x)=1;
   
3.         for n=1:2013
   
4.                 a(x)=mod(x*a(x),2013);
   
5.         end
   
6.         b(a(x)+1)=1;
   
7. end
   
8. sum(b)

复制代码

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

cn8888

\[\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

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

\[{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

\(\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\)