5
$\begingroup$

I have been trying to prove a certain claim and have hit a wall. Here is the claim...

Claim: If $n$ is a positive integer then $\log_{7}n$ is an integer or it is irrational

Proof (so far): Let $y=\log_{7}n$. Note that to say $n$ is a positive integer is equivalent to saying that n is a non-zero natural number. We will proceed by trying to prove the contrapositive.

Claim (alternate version): If $y$ is a rational number and is not an integer, then either $n$ is zero or it is not a natural number.

Given the above we can assume that there exist integers $a$ and $b$ such that $y$ equals the quotient of $a$ over $b$. We can also assume from the premises that $b$ does not equal one and that $a$ and $b$ are relatively prime. Note thus that $n$ may be considered equal to seven raised to the power of $a$ over $b$. Further note that because of this $n$ cannot be zero or negative. To prove the claim, one must prove that $n$ is not a natural number.

Where I am stuck: How can I guarantee from here that $n$ is not a natural number? Is there any way to concretely ensure that there are no integers $a$ and $b$ such that the fractional exponent above will never give an integer when raising seven to its power?

I have been trying to play around with a proof that there is no such thing as a rational root of a prime number, but that hasn't shook anything loose so far.

$\endgroup$
  • $\begingroup$ Is \log_7n meant to be $\log_7 n$? $\endgroup$ – 6005 Aug 11 '15 at 16:28
  • $\begingroup$ Yes. I am having a little trouble with the LaTeX. $\endgroup$ – Johnq Aug 11 '15 at 16:28
  • $\begingroup$ Johnq, I hope your question looks okay now. Sorry for all the editing. $\endgroup$ – 6005 Aug 11 '15 at 16:36
8
$\begingroup$

Suppose $\log_7 n =\frac{p}{q}$ is rational, then $7^{p/q}=n$, raising both sides to the $q^{\text{th}}$ power, we see that $7^p=n^q$. Now we have by unique prime factorization that $n=7^k$ for some integer $k$, since it divides $7^p$. But then $7^p=7^{kq}$, or $p=kq$, but then $\frac{p}{q}=k$ is an integer as desired.

$\endgroup$
  • $\begingroup$ Are you starting from my original claim? $\endgroup$ – Johnq Aug 11 '15 at 17:07
  • $\begingroup$ @Johnq yes, I'm showing that if $\log_7 n$ is rational, it must be an integer. $\endgroup$ – jgon Aug 12 '15 at 7:43
2
$\begingroup$

Usually negative statements are proven by contradiction.

The definition of an irrational number is a number which is not rational. This suggest that you should try contradiction.

Proof start

Assume by contradiction that $\log_7 (n) =\frac{a}{b}$ with $a,b \in \mathbb Z$ and $b \nmid a$.

This implies that $$7^{\frac{a}{b}}=n$$ or $$n^b=7^a$$

What does this tell you about the prime factorisation of $n$? From here it should be easy.

$\endgroup$
  • $\begingroup$ So would you say that the contrapositive in this case was the wrong way to go? $\endgroup$ – Johnq Aug 11 '15 at 16:57
  • $\begingroup$ I am a bit stumped at what you mean by "what does this tell you about the prime factorization of n". I see that 7 divides $n^b$ ,but from there I don't see what that says about n, a, or b. $\endgroup$ – Johnq Aug 11 '15 at 17:20
  • $\begingroup$ Would it suggest that n can only be comprised of roots of 7? $\endgroup$ – Johnq Aug 11 '15 at 17:25
  • $\begingroup$ @Johnq Contrapositive probably also works. But most of the times if contrapositive works, so does contradiction. $\endgroup$ – N. S. Aug 11 '15 at 17:53
  • $\begingroup$ @Johnq If $p |n$ then $p|n^b=7^a$. This shows that the only prime dividing $n$ is $7$. $\endgroup$ – N. S. Aug 11 '15 at 17:54
0
$\begingroup$

The contrapositive is an awkward approach to take in this problem, because the alternatives are $\log_7 n$ is either an integer or irrational in the conclusion.

So the contrapositive would be to assume $\log_7 n$ is a rational number which is not an integer, and then try to prove $n$ is not a positive integer.

An approach using the Rational Root Theorem seems easier to explain.

Let's assume that $n$ is a positive integer and that $x = k/m$ is rational, i.e. the ratio of two coprime integers, say $m \gt 0$, and then show that in fact $x$ would have to be an integer. Note that:

$$ x = \log_7 n \implies 7^x = 7^{k/m} = n \implies n^m - 7^k = 0 $$

Now $n$ satisfies a polynomial. If $k \ge 0$, then this polynomial has integer coefficients, and since the leading coefficient is one, any rational root $n$ would have to be an integer of the form $n \mid 7^k$. Since $n$ is known to be a positive integer, then $n = 7^d$ for some integer $d$ between $0$ and $k$, and thus $x = \log_7 n = d$ is an integer.

On the other hand, suppose $k \lt 0$. Then we convert the above to an integer polynomial by multiplying by $7^{-k}$:

$$ 7^{-k} n^m - 1 = 0 $$

Now the Rational Roots Theorem says $n$ must have the form $\frac{\pm 1}{7^d}$ where $d$ is an integer between $0$ and $-k$. But we have assumed $n$ is a positive integer (in this proof by contradiction), so the sign of $n$ must be positive and $d$ must be zero. That is, $n=1$ and $x = \log_7 n = 0$, which is an integer.

Therefore if $n$ is a positive integer, then $x = \log_7 n$ is either irrational or it is an integer. QED

$\endgroup$
  • $\begingroup$ What part of this serves as the proof that n could be irrational? $\endgroup$ – Johnq Aug 11 '15 at 18:28
  • $\begingroup$ As I explain in the opening paragraph, my preferred approach is not a strict contrapositive as you tried to pursue. I agree with what you state as the strict contrapositive, restating this in the second paragraph. In the fourth paragraph I give the logically equivalent statement, in which we will assume both $\log_7 n$ is rational and $n$ is a positive integer, and prove that then $\log_7 n$ is an integer. $\endgroup$ – hardmath Aug 11 '15 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.