2
$\begingroup$

Q: Prove that $\frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n$ is an integer for every integer n. In fact, I already have a method, but it seems too long. So I would first (1)is there any problem with my logic? (2) Is there any better/faster method to do these kinds of questions?

My solution: $$\frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n$$ $$=\frac{1}{15}(3n^5+5n^3+7n)$$ Then my next time is to use M.I to prove that $(3n^5+5n^3+7n)$ is divisible by $15$ for positive integers. And for negative integer, I switch it into -$(3n^5+5n^3+7n)$ and it also satisfies the divisibility of $15$.

But the above seems too clumsy. This course is "Intro to number theory". Is there any beter method to do it?

$\endgroup$

marked as duplicate by Jyrki Lahtonen, Community Sep 15 '18 at 15:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Well, in this cases, you should try using induction over $n$. The case when $n =1$ its obvius, so, use the hypothesis that $15| 3n^5+5n^3+7n$ for some $n$ and prove that $15|3(n+1)^5+5(n+1)^3+7(n+1)$. $\endgroup$ – Gustavo Mezzovilla Sep 15 '18 at 14:15
  • 2
    $\begingroup$ Does M.I. stand for "mathematical induction"? If so, I'd say that this was not optimal. To show that the quintic yields values divisible by $15$ is the same as to show the values are divisible by both $3$ and $5$. Both of those are simple, finite, checks. $\endgroup$ – lulu Sep 15 '18 at 14:15
  • $\begingroup$ divisible by 3 and 5 ?! That's a good idea. Let me think about it $\endgroup$ – Jason Ng Sep 15 '18 at 14:18
  • $\begingroup$ Have you learnt modular arithmetic? $\endgroup$ – user579462 Sep 15 '18 at 14:20
  • 1
    $\begingroup$ Approach0 is your friend. See Bill's answer in particular! $\endgroup$ – Jyrki Lahtonen Sep 15 '18 at 14:47
4
$\begingroup$

Modulo $3$, your numerator is:

$$3n^5+5n^3+7n \equiv -n(n^2-1) $$

$$\equiv -n(n-1)(n+1)\pmod{3}.$$

The last expression is a product of three consecutive integers and hence divisible by $3$.

Modulo $5$, you have

$$3n^5+5n^3+7n \equiv -2n^5+2n $$ $$\equiv -2n(n^4-1) \pmod{5}.$$

If $n$ is divisible by $5$, then so is the last expression. If $n$ is not divisible by $5$, then $n^4 \equiv 1 \pmod{5}$ and still the last expression is divisible by $5$.

Since the numerator is divisible by both $3$ and $5$, it's divisible by $15.$

$\endgroup$
2
$\begingroup$

You can use Little Fermat in the form $n^p\equiv n\bmod p$ ($p$ prime, which works for all $n$ as opposed to $n^{p-1}\equiv 1 \bmod p$ for $n$ not divisible by $p$)

For the prime $5$, we have $n^5\equiv n \bmod 5$ so you get $$3n^5+5n^3+7n\equiv 3n+7n\equiv 0\bmod 5$$

For the prime $3$ we have $n^3\equiv n\bmod 3$ so that $$3n^5+5n^3+7n\equiv 5n+7n\equiv 0 \bmod 3$$

Combine these and you have your answer.

$\endgroup$
  • $\begingroup$ I am still learning modular arithmetic (just begin the learning). I find the Fermat theorem. And using $n^5 \equiv n$, I can write $3n^5 \equiv 3n$ since $(3,5)=1$ relatively prime. Then, it implies $3n^5-3n=5c$ for some integer $c$. But I cannot understand how to create $$3n^5+5n^3=7n \equiv 3n+7n \equiv 0 mod 5$$ $\endgroup$ – Jason Ng Sep 15 '18 at 14:40
  • $\begingroup$ @JasonNg Well $5n^3$ goes to $0$ because it is divisible by $5$ and $3n^5\equiv 3n$ $\endgroup$ – Mark Bennet Sep 15 '18 at 14:53
  • $\begingroup$ Can I interpret like this: $$n^5 \equiv n $$ mod 5 $$3n^5 \equiv 3n$$ mod 5 (since (3,5) are relative prime) $$3n^5-3n \equiv 0 $$ mod 5 $$ 3n^5+5n^3-3n \equiv 0$$ mod 5 (since 5n^3 is a mutliple of 5, so it won't affect anything) $$3n^5=5n^3+7n \equiv 10n \equiv 0$$ mod 5 $\endgroup$ – Jason Ng Sep 15 '18 at 14:56
  • $\begingroup$ by the way, how do put "mod 5" next to the equation in the middle...it seems I fail to do it $\endgroup$ – Jason Ng Sep 15 '18 at 14:57
  • 1
    $\begingroup$ @JasonNg For text you can use \text{} within the dollar signs and what goes in the brackets comes out as text (including spaces). I used \bmod to get the mod $5$ text in the right place - there are generally specific commands for common mathematical text and functions. $\endgroup$ – Mark Bennet Sep 15 '18 at 15:26
1
$\begingroup$

For a degree $n$ polynomial $f$ to be "integer-valued", all you need to check is that $f(a)\in\Bbb Z$ for $n+1$ consecutive integers $a$. This is because $$\sum_{j=0}^{n+1}(-1)^j\binom{n+1}jf(x+j)=0\tag{*}$$ and if you have $n+1$ consecutive integer values for $f$, then upwards and downwards induction gives $f(a)\in\Bbb Z$ for all $a\in\Bbb Z$.

In your example, $f(0)=0$, $f(\pm1)=1$, $f(\pm2)=\pm10$ and $f(\pm3)=\pm 59$ which is more than enough.

$\endgroup$
0
$\begingroup$

Hint: Your term is equal $$\frac{n}{15}(3n^4+5n^2+7)$$ and now Show that that $$15|n(3n^4+5n^2+7)$$ for all $n$

$\endgroup$
  • $\begingroup$ Sure. I firstly try $3n^4+5n^2+7$, but it doesn't work well. So I try $3n^5+5n^2+7n$, which works well. By the way, someone suggests me to try figuring out the divisibility of 3 and 5 $\endgroup$ – Jason Ng Sep 15 '18 at 14:19
  • $\begingroup$ $$n(3n^4+5n^2+7)$$ must also work! $\endgroup$ – Dr. Sonnhard Graubner Sep 15 '18 at 14:23
0
$\begingroup$

Use induction for $n\in \mathbb Z^+$.

Base case: $$P(1)=\frac{1}{15}(3\cdot 1^5+5\cdot 1^3+7\cdot 1)=1.$$ Inductive hypothesis: $$P(n)=\frac{1}{15}(3n^5+5n^3+7n) \in \mathbb Z^+.$$ Inductive step: $$P(n+1)=\frac{1}{15}(3(n+1)^5+5(n+1)^3+7(n+1))=\\ =\underbrace{\frac{1}{15}(3n^5+5n^3+7n)}_{P(n)\in \mathbb Z^+}+\\ \frac{1}{15}(15(n^4+2n^3+2n^2+n)+15(n^2+n)+15) \in \mathbb Z^+.$$ Since the powers of $n$ in $P(n)$ are odd, it will be true for negative integers as well.

$\endgroup$

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