Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Integer (except 0) raised to a power and then divide by that power?
If ( x^n) / n , can you predict the quotient and/or its remainder?
1 Answer
- jordanLv 41 decade agoFavorite Answer
if n is prime then the answer is trivial by fermat.
let d=gcd(x,n), so it exists X and N such that x=dX, n=dN.
we are looking for the remainder r of dX^(dN) mod (dN), so if 0<= r < dN we have that (x^n-r)/n is integer, so ((d^(dN)X^(dN) -r)/(dN)) is integer.obviusly d|r: let r=dR, so ((d^(dN-1)X^(dN)-R) / N) is integer, with gcd(X,N)=1. let gcd(d,N)=D, so d=Dk, N=Dy then (Dk^(DDky)X^(DDky))-R)/(Dy) is integer.so D|R, R=hD.
it follows that y | D^(DDky-1) (kX)^(DDky) -h, with gcd (y,k)=gcd (y,h)=gcd(k,h)=1, and the remainder is such that dD | r.
i don't see other elementary step altough if we subtract phi(n) don't help.
