# How to prove an integer is (not) a power of some other integer?

I assume that is nigh-impossible to prove when the conditions on the integers are very general. However, my algebra professor told me that the following is true:

If $n$ is a composite positive integer, $(n - 1)! + 1$ is not a power of $n$.

I assume this is an easy number theory problem, but I don't know how to approach it. The form of $(n-1)!+1$ makes me think of somehow splitting the term into its primes and using Wilson's, however improbable it is to do so. And for a proof by contradiction, finding parameters on $x$ such that $n^x=(n-1)!+1$ gets me nowhere, since it would just translate to a discrete log problem.

I appreciate any hints or input!

-

## 2 Answers

HINT Since $n$ is composite, consider a prime dividing $n$. Will it divide $(n-1)! + 1$? (Remember that the prime dividing $n$ will occur in $(n-1)!$ and hence will divide $(n-1)!$).

-
I think I have it now. Thanks! I'm not sure if I'm allowed to post full solutions, so I deleted my last comment. All one needs to do is prove a prime factor of $n$ doesn't divide $(n-1)!+1$ by your tip. Hence, it isn't a power of $n$ since the prime factor must divide powers of $n$. –  Dustin Tran Jun 30 '12 at 7:33
That's kind of a heavy-handed hint :P –  Ben Millwood Jun 30 '12 at 9:57

The number $(n-1)! + 1$ cannot even be divisible by $n$, nevermind actually being $n$ or a power of $n$.

See this new question for proof of this fact (at least for $n\geq 5$):

link

-
So $4$ divides $6$, interesting. –  Marc van Leeuwen Jun 30 '12 at 9:38
If you read the comments on the linked question you will see that $n=4$ is the only case that this doesn't work... –  fretty Jun 30 '12 at 9:42
Then you should have said so. –  Marc van Leeuwen Jun 30 '12 at 10:39
Why should I have? My answer said to follow the link and read the corresponding post for a related result, I did not claim the entire truth of this other result. It is a small amount of common sense from there to prove the $n=4$ case of the present question is not true either. –  fretty Jun 30 '12 at 11:03
OK, I somewhat misread what you said, my excuses. "If $n$ is composite, then $n$ divides $(n−1)!$" is not a claim you make, but just the title of a question you link to. Since it is a false statement, I think it would be best here to actually change the clickable text, adding somthing like "unless $n=4$", or make clear in some other way that you don't claim this yourself. –  Marc van Leeuwen Jun 30 '12 at 16:50