Can someone help me to prove that $\displaystyle n^2+3n+5$ is not divisible by 121 for any $\displaystyle n \in Z$ ?

Printable View

- May 19th 2006, 03:31 AMOReillyDivisibility by 121
Can someone help me to prove that $\displaystyle n^2+3n+5$ is not divisible by 121 for any $\displaystyle n \in Z$ ?

- May 19th 2006, 05:19 AMCaptainBlackQuote:

Originally Posted by**OReilly**

then the exists a $\displaystyle \kappa$ such that:

$\displaystyle

n^2+3n+5=121\ \kappa

$

So from the quadratic formula we have:

$\displaystyle

n=\frac{-3 \pm \sqrt{9-4(5-121\ \kappa})}{2}

$

Which implies that $\displaystyle \sqrt{9-4(5-121\ \kappa})$ is an odd integer, $\displaystyle m$ say. So:

$\displaystyle

121\times4\times \kappa - 11=m^2

$

but the LHS is divisible by $\displaystyle 11$, and as $\displaystyle m^2$ is a square it is also divisible

by $\displaystyle 121$ (which is $\displaystyle 11^2$), but that would imply that $\displaystyle 11$ is divisible by $\displaystyle 121$; a

contradiction, so no such $\displaystyle n$ exits.

RonL - May 20th 2006, 01:28 PMOReilly
Can you just explain me this part, I didn't quite understand it. :confused:

Quote:

Originally Posted by**CaptainBlack**

- May 20th 2006, 01:38 PMrgepQuote:

Can someone help me to prove that $\displaystyle n^2+3n+5$ is not divisible by 121 for any $\displaystyle n \in Z$ ?

- May 20th 2006, 01:53 PMCaptainBlackQuote:

Can you just explain me this part, I didn't quite understand it. :confused:

Quote:

Originally Posted by**CaptainBlack**

prime. It's a consequence of the fundamental theorem of arithmetic, that

the decomposition of a number into a product of primes is essential unique.

So the left hand side of the equation being divisible by 11 implies that the

right hand side is also divisible by 11, but the right hand side is a square.

So the right hand side is divisible by 121 (the square of 11). This implies

that the left hand side is divisible by 121, and so that 11 is divisible by

121 which is a contradiction.

RonL - May 20th 2006, 05:42 PMOReilly
When I was trying to solve the problem I have done this:

$\displaystyle \begin{array}{l}

n^2 + 3n + 5 = 121k \\

n^2 - 8n + 11n + 16 - 11 = 121k \\

(n - 4)^2 + 11n - 11 = 121k \\

(n - 4)^2 = 121k - 11n + 11 \\

(n - 4)^2 = 11(11k - n + 1) \\

\end{array}

$

But I have stoped there.

Let me see if I have understood good.

$\displaystyle 11(11k - n + 1)$ is obviosly divisible by 11, so $\displaystyle (n - 4)^2 $ is also divisible by 11. But $\displaystyle (n - 4)^2 $ is also divisible by $\displaystyle 11^2 $ which now implies that $\displaystyle 11(11k - n + 1)$ is divisible by 121. So we get that $\displaystyle \frac{{11}}{{121}} = \frac{{11k - n + 1}}{{(n - 4)^2 }}$ which shows that 11 is not divisible by 121.

Is that correct?

I didn't know that if a square is divisible by a prime, it is also divisible by the square of the prime. Boy, I feel stupid and embarrassed now! :o

Divisibility of numbers is simply killing me, I just can't solve any harder problem. I am not expert, but I think that in order to solve those problems you need to know Number theory. Since I am on level of Algebra 1 and 2 for high school (problem that I have posted is from Algebra 1) I find that many harder problems constructed for learning Algebra 1 and 2 that concerns divisibility are based on writers thorought knowledge of Number theory. I don't know if I am wrong, but that's my impression. Either that, or I must find excuse! - May 20th 2006, 06:41 PMThePerfectHackerQuote:

Originally Posted by**OReilly**

Let $\displaystyle p|ab$ then, $\displaystyle p|a$ or $\displaystyle p\not | a$. If $\displaystyle p\not |a$ then, $\displaystyle \gcd(a,p)=1$ then, $\displaystyle p|b$ by Euclid's Lemma. Thus, $\displaystyle p|a \mbox{ or }p|b$.

Thus, given $\displaystyle p|a^2$ you have, $\displaystyle p|aa$ thus, $\displaystyle p|a$ or $\displaystyle p|a$ thus, $\displaystyle p|a$ definetly. Now, if $\displaystyle c|d$ then, $\displaystyle c^n|d^n$ but since $\displaystyle p|a$ then $\displaystyle p^2|a^2$ if you want to be formal about it ;)

Quote:

Originally Posted by**OReilly**

- May 20th 2006, 11:14 PMCaptainBlackQuote:

When I was trying to solve the problem I have done this:

$\displaystyle \begin{array}{l}

n^2 + 3n + 5 = 121k \\

n^2 - 8n + 11n + 16 - 11 = 121k \\

(n - 4)^2 + 11n - 11 = 121k \\

(n - 4)^2 = 121k - 11n + 11 \\

(n - 4)^2 = 11(11k - n + 1) \\

\end{array}

$

But I have stoped there.

Let me see if I have understood good.

$\displaystyle 11(11k - n + 1)$ is obviosly divisible by 11, so $\displaystyle (n - 4)^2 $ is also divisible by 11. But $\displaystyle (n - 4)^2 $ is also divisible by $\displaystyle 11^2 $ which now implies that $\displaystyle 11(11k - n + 1)$ is divisible by 121. So we get that $\displaystyle \frac{{11}}{{121}} = \frac{{11k - n + 1}}{{(n - 4)^2 }}$

Quote:

which shows that 11 is not divisible by 121.

Is that correct?

I didn't know that if a square is divisible by a prime, it is also divisible by the square of the prime. Boy, I feel stupid and embarrassed now! :o

- May 21st 2006, 04:26 AMOReillyQuote:

Originally Posted by**CaptainBlack**

Let me try again.

From my example we have:

$\displaystyle \begin{array}{l}

(n - 4)^2 - 11 = 121k - 11n \\

(n - 4)^2 - 11 = 11(11k - n) \\

\end{array}

$

That implies that $\displaystyle (n - 4)^2 - 11$ is divisible by 11. But $\displaystyle (n - 4)^2$ is also divisible by 121 but we would have that $\displaystyle (n - 4)^2 - 11$ is also divisble by 121, which is different.

Is that ok? - May 21st 2006, 09:11 AMThePerfectHacker
Not necessarily, you proof falls:

Quote:

But $\displaystyle (n-4)^2$ is also divisible by 121 but we would have that $\displaystyle (n-4)^2-11$.is also divisble by 121

- May 21st 2006, 02:11 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

- May 21st 2006, 02:24 PMThePerfectHacker
If,

$\displaystyle a|b,a\not |c$ then, $\displaystyle a\not |(b+c)$

According to you,

$\displaystyle a|b,a\not |c$ then, $\displaystyle a|(b+c)$

Where,

$\displaystyle a=121$

$\displaystyle b=(n-4)^2$

$\displaystyle c=11$

Again in Line,

Quote:

But $\displaystyle (n-4)^2$ is also divisible by 121 but we would have that $\displaystyle (n-4)^2-11$.is also divisble by 121

- May 21st 2006, 02:55 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

- May 21st 2006, 03:58 PMThePerfectHacker
From the equation,

$\displaystyle

\begin{array}{l} (n - 4)^2 - 11 = 121k - 11n \\ (n - 4)^2 - 11 = 11(11k - n) \\ \end{array}

$

Your proof.

1)RHS is divisible by 11,

2)So LHS is divisible by 11,

3)$\displaystyle 11|((n-4)^2-11)$

4)Since, $\displaystyle 11|(-11)$ so, $\displaystyle 11|(n-4)^2$

5)So, 121 divides $\displaystyle (n-4)^2$

6)But then, 121 divides 11.

7)Contradiction.

Explain to me step 6! - May 21st 2006, 04:20 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

I don't know what I have to explain?