Divisible by 49

**OReilly** · August 23rd 2006, 06:45 PM

Can someone show me the proof by mathematical induction that $n^2+n+2$ isn't divisible by 49 for every n (natural number).

**ThePerfectHacker** · August 23rd 2006, 06:55 PM

Originally Posted by OReilly

Can someone show me the proof by mathematical induction that $n^2+n+2$ isn't divisible by 49 for every n (natural number).

You can greatly simplify your problem to reducing it to showing that $7\not |n^2+n+2$

**OReilly** · August 23rd 2006, 07:09 PM

Originally Posted by ThePerfectHacker

You can greatly simplify your problem to reducing it to showing that $7\not |n^2+n+2$

But it can be divisible by 7. For example for n=3.

**ThePerfectHacker** · August 23rd 2006, 07:23 PM

Originally Posted by OReilly

But it can be divisible by 7. For example for n=3.

I know, but once you exceede 49 it is always true.

I was just writing out a proof. But I accidently closed my internet thing and lost everything I typed.

**rgep** · August 23rd 2006, 10:32 PM

Firstly observe that n^2+n+2 is divisible by 7 if and only if n is congruent to 3 modulo 7: that is, if n is of the form 7x+3. See this by writing it as n^2 - 6n + 9 + 7(n-1), so that it is (n-3)^2 modulo 7.

Now substitute n=7x+3 into n^2 + n + 2 to get 49x^2 + 49x + 14, which cannot be divisible by 49.

**OReilly** · August 24th 2006, 06:23 AM

Is this proof valid?

Supose that for $n=k$ expression is divisible by 49:
$k(k + 1) + 2 = 49a$

Supose that now for $n=k+1$ expression is also divisible by 49:
$(k + 1)(k + 2) + 2 = 49b$

From first equation we get that $k + 1 = \frac{{49a - 2}}{k}$ .

Substituting into second equation we get:
$\begin{array}{l} (\frac{{49a - 2}}{k})(k + 2) + 2 = 49b \\ \frac{{49ak + 98a - 2k - 4}}{k} = 49b - 2 \\ 49ak + 98a - 2k - 4 = 49bk - 2k \\ 49ak + 98a - 2k - 4 - 49bk + 2k = 0 \\ 49ak + 98a - 49bk - 4 = 0 \\ \end{array} $

Last expression isn't divisible by 49 so $n^2+n+2$ isn't divisible by 49.

**ThePerfectHacker** · August 24th 2006, 02:40 PM

You need to show that,
If,
$n^2+n+2\not = k$
then,
$n^2+n+2\not = k+1$

Equivalently (contropositive),
If,
$n^2+n+2=k+1$
then,
$n^2+n+2=k$

You shown that:
if,
$n^2+n+2=k$
then,
$n^2+n+2\not = k+1$
This is not equivalent to the above two statements.

**Quick** · August 24th 2006, 05:10 PM

I don't understand your proof.

where am I off?

If $n^2+n+2=k$
then, $n^2+n+3=k+1$

**ThePerfectHacker** · August 24th 2006, 05:57 PM

Here is how you do it.
---
You need to show there doth not exist such a $49k$ such as,
$n^2+n+(2-49k)=0$
Which means there are no integral solution for $n$ .
If you solve for "n",
$n=\frac{-1\pm \sqrt{1-4(2-49k)}}{2}$ .
Note the following, if the expression in the radical is a square then "n" is an integral number because the square root of an odd square is an odd whole number and when added of subtracted to 1 produces an even number and when finally divided by two produces an integral number, thus, if
$1-4(2-49k)=196k-7$ is not a square then,
$1-4(2-49(k+1))=1-4(-47-49k)=196k+189$ is also not a square.
Thus, again you need to show that.
IF,
$196k-7$ is not a square
THEN,
$196k+188$ is not a square.
~~Contropositive Time~~
IF,
$196k+188$ is a square.
THEN,
$196k-7$ is a square.

For some reason I cannot continue. I am hoping someone will see this and tell me the next step.

**CaptainBlack** · August 24th 2006, 09:15 PM

Originally Posted by OReilly

Is this proof valid?

Supose that for $n=k$ expression is divisible by 49:
$k(k + 1) + 2 = 49a$

Supose that now for $n=k+1$ expression is also divisible by 49:
$(k + 1)(k + 2) + 2 = 49b$

From first equation we get that $k + 1 = \frac{{49a - 2}}{k}$ .

Substituting into second equation we get:
$\begin{array}{l} (\frac{{49a - 2}}{k})(k + 2) + 2 = 49b \\ \frac{{49ak + 98a - 2k - 4}}{k} = 49b - 2 \\ 49ak + 98a - 2k - 4 = 49bk - 2k \\ 49ak + 98a - 2k - 4 - 49bk + 2k = 0 \\ 49ak + 98a - 49bk - 4 = 0 \\ \end{array} $

Last expression isn't divisible by 49 so $n^2+n+2$ isn't divisible by 49.

It looks to me that what you have proven is that $k^2+k+2$ is not divisible
by $49$ for consecutive integral values of $k$ .

RonL

**CaptainBlack** · August 24th 2006, 09:35 PM

Originally Posted by Quick

I don't understand your proof.

where am I off?

If $n^2+n+2=k$
then, $n^2+n+3=k+1$

From his silence on this and departure off on another tangent I think
ImPerfectHacker agrees with you and he doesn't understand his
argument either

It is either so subtle that we can't see the point, or its wrong. I know
where I'm putting my money (no not in that box under the bed).

RonL

**ThePerfectHacker** · August 25th 2006, 04:32 AM

Look at post #7. I say it is no good.
---
I still do not see why you chose such a method. The quickest would be quadradic reciprocity.

**Glaysher** · August 25th 2006, 05:54 AM

Originally Posted by ThePerfectHacker

You need to show that,
If,
$n^2+n+2\not = k$
then,
$n^2+n+2\not = k+1$

Equivalently (contropositive),
If,
$n^2+n+2=k+1$
then,
$n^2+n+2=k$

You shown that:
if,
$n^2+n+2=k$
then,
$n^2+n+2\not = k+1$
This is not equivalent to the above two statements.

Don't you mean

Need to prove either

statement true for n = k implies statement true for n = k + 1

or

Contropositive
Statememt not true for n = k + 1 implies statement not true for n = k

OReilly showed

Statement true for n = k implies statement not true for n = k + 1

**Quick** · August 25th 2006, 06:34 AM

Originally Posted by Glaysher

Don't you mean

Need to prove either

statement true for n = k implies statement true for n = k + 1

wouldn't it imply that n+1=k+1???

**Glaysher** · August 25th 2006, 08:56 AM

Originally Posted by Quick

wouldn't it imply that n+1=k+1???

I assume you are unfamiliar with the principle of mathematical induction

Usually you are trying to prove something for all natural numbers n

You show that it is true when n = 1

Then you assume it is true for some n = k

It is okay to assume this as we have already proved it for n = 1 so we already know there is at least one possible value for k.

We then try to prove that it also holds for n = k + 1 assuming that it holds for n= k.

Once we have done this we have proved it for all natural numbers n as

True for n = 1 means true for n = 2 means true for n = 3 and so on ...

This method can be adapted to suit several different purposes

Thread: Divisible by 49

LinkBack

Thread Tools

Display

Divisible by 49

I don't get it...

Similar Math Help Forum Discussions

Show that pos int divisible by 3 iff sum of digits divisible by 3

Divisible by 9

Proof that m is divisible by 3 iff m^2 is divisible by 3

Prove that if x's square is divisible by a, then x is also divisible by a

# of binomial coefficients not divisible by 3 is not divisible by 5

Search Tags