r>=1时,数x和p^r互素能推出x和p互素,因为若(x,p^r)=1,则存在u,v使得u*x+v*p^r=1,即u*x+(v*p^(r-1))*p=1,即存在m=u和n=v*p^(r-1)使得m*x+n*p=1成立,所以(x,p)=1.反过来数x和p互素能推出x和p^r互素,因为若x和p^r不互素,则可设(x,p^r)=n>1,设m是n的一个质因子,m也是p^r的质因子,而p^r的质因子只有p,故m=p,又m|x,所以p|x,这与x和p互素矛盾.
在0到（p^r）-1中与p^r互素数的数的个数即等于和p互素的个数.
0到（p^r）-1中和p不互素的有0,p,2p,3p,……,p^r-p,总共有p^r/p=p^(r-1)个 ,互素的就有p^r-p^(r-1)=(p-1)*p^(r-1)个