r>=1時,數(shù)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.反過來數(shù)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互素數(shù)的數(shù)的個數(shù)即等于和p互素的個數(shù).
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)個