[(2*(n^2)+1] MUST be divisible by 3

**Almutairi** · Apr4-09, 11:26 AM

Hi,
while trying to answer a home work question I came up with an unrelated equation, although it is very trivial it seemed interesting to me:

If n is an integer not divisible by 3 and not equal to 0, then [(2*(n^2)+1] MUST be divisible by 3.

I tried to proof it using the fact that
(n^3)/3 + (n^2)/2 + n/6 is always an integer. It seemed good but I stopped in the second page!
So my question is there a nicer shorter way to proof it?

Thanks

**signerror** · Apr4-09, 11:36 AM

Two cases:

$LaTeX Code: n \\equiv 1 \\mod 3 \\Rightarrow n^2 \\equiv 1 \\mod 3$
$LaTeX Code: n \\equiv 2 \\mod 3 \\Rightarrow n^2 \\equiv 1 \\mod 3$

Either way, $LaTeX Code: n^2 \\equiv 1 \\mbox{ mod } 3$ . Now just plug this in...

**tiny-tim** · Apr4-09, 11:47 AM

Hi Almutairi! Welcome to PF!

(try using the X² tag just above the Reply box

)

Originally Posted by Almutairi

If n is an integer not divisible by 3 and not equal to 0, then [(2*(n^2)+1] MUST be divisible by 3.

Sorry, but 2^(2²) + 1 = 16 + 1 = 17

Generally, 2²ⁿ - 1 = 4ⁿ - 1 is divisible by 3, and so is 2²ⁿ⁺¹ + 1, as you can see by writing 4 in ternary (ie, it's "11" in base3).

**signerror** · Apr4-09, 11:54 AM

Originally Posted by tiny-tim

Sorry, but 2^(2²) + 1 = 16 + 1 = 17

$LaTeX Code: 2\\cdot n^2 \\mbox{, not } 2^{n^2}$

**Almutairi** · Apr5-09, 04:37 AM

Sorry, but 2(22) + 1 = 16 + 1 = 17
Generally, 22n - 1 = 4n - 1 is divisible by 3, and so is 22n+1 + 1, as you can see by writing 4 in ternary (ie, it's "11" in base3).

thanx for the welcome, and sorry for the confusion

but I meant 2n², and also you used 2 as a value of n but 2 is not divisible by 3 (i.e 2/3 is not an integer). So for example
let n=7( seven is not zero and not divisible by 3)
so (7²)*2=98 and 98+1=99 which is divisible by 3.
also the opposite statement can be made so together:

1) If n is an integer not divisible by 3 and not equal to 0 then [2n²+1] is Always a multiple of 3

2) if n is an integer divisible by 3 and not equal to zero then [2n²+1] is NEVER a multiple of 3.

To explain this great theorem

you could relate it to odd and even numbers(divisible by 2 or not) the same here, you could divide integers into numbers divisible by 3 or not, however, to transform an integer from the first category to the second you (double its square and add one) instead of just adding one.
I proved it using the fact that (n³)/3 + (n²)/2 + n/6 is always an integer, but as I said it was long, I will post it later.

**Almutairi** · Apr5-09, 04:41 AM

Originally Posted by signerror

Two cases:

$LaTeX Code: n \\equiv 1 \\mod 3 \\Rightarrow n^2 \\equiv 1 \\mod 3$
$LaTeX Code: n \\equiv 2 \\mod 3 \\Rightarrow n^2 \\equiv 1 \\mod 3$

Either way, $LaTeX Code: n^2 \\equiv 1 \\mbox{ mod } 3$ . Now just plug this in...

I am sorry I didn't understand what you were trying to do could you please explain it differently.

**tiny-tim** · Apr5-09, 05:16 AM

Originally Posted by Almutairi

I am sorry I didn't understand what you were trying to do could you please explain it differently.

Write n in ternary …

if it ends in 1 or 2, then n² ends in 1

**bigubau** · Apr5-09, 08:44 AM

What if you take the 2 possible cases

and

, where 'p' is arbitrary in the set of natural numbers

?

**Gear300** · Apr5-09, 05:10 PM

You could prove it with less paper (supposedly) by using
1 = 1²
1 + 3 = 2²
1 + 3 + 5 = 3²
1 + 3 + 5 + 7 = 4²...and so forth with this pattern

**Almutairi** · Apr5-09, 08:43 PM

Proof

Given that [(n³)/3 + (n²)/2 + n/6] is an integer, then

[ 2n³ + 3n²+ n] is an integer that is a multiple of 6

and therefore, [2n³+ n] is a multiple of 3

and it can be written as n[2n³ + 1]

so either n or [2n² + 1] is a multiple of 3, or both.

To rollout the possibility of both being a multiple of 3 we need another proof:

Let both n and [2n² + 1] be multiples of 3,

then 2n² is NEVER a multiple of 3……………………...(A)

However, by a counter example we can show this is not true

(e.g. 2*3²=18), so either it is sometimes true or always true. For obvious

reasons it can’t be sometimes true and sometimes not true, so

2n² is always a multiple of 3…………………………. (B)

Statements A and B are clearly in contradiction.

so either n or [2n² + 1] is a multiple of 3.

**ramsey2879** · Apr5-09, 10:50 PM

Originally Posted by Almutairi

Proof

Given that [(n³)/3 + (n²)/2 + n/6] is an integer, then

[ 2n³ + 3n²+ n] is an integer that is a multiple of 6

and therefore, [2n³+ n] is a multiple of 3

and it can be written as n[2n³ + 1]

so either n or [2n² + 1] is a multiple of 3, or both.

To rollout the possibility of both being a multiple of 3 we need another proof:

Let both n and [2n² + 1] be multiples of 3,

then 2n² is NEVER a multiple of 3……………………...(A)

However, by a counter example we can show this is not true

(e.g. 2*3²=18), so either it is sometimes true or always true. For obvious

reasons it can’t be sometimes true and sometimes not true, so

2n² is always a multiple of 3…………………………. (B)

Statements A and B are clearly in contradiction.

so either n or [2n² + 1] is a multiple of 3.

Great proof. You have a talent for math to have noted this. As you learn more number theory you will find the mod operator mentioned by Signerror to be a powerful tool not to be ignored. Basically as you subtract or add n to any number it stays equivalent mod n. Thus X =* X + nt mod n where X, n and t are integers. Usually we write three parallel lines like the equal sign to show equivalence but some people justuse the "=" sign where it is understood to mean equivalence and not equals. We say that a set of numbers is a complete residue system mod n whenever any integer mod n must be equivalant to one of the members of the set. Now since it is always possible to add or subtract n from any integer to get a number between and including 0 and n-1 then the set of numbers from 0 to n-1 is a complete set of residues mod n. Thus 0 through 2 is the complete set of residues mod 3. If a number is divisible by 3 then N =* 0 mod 3, otherwise N =* 1 or 2 mod 3. So we can substitue either 3t + 1 or 3t+2 for any number not divisble by 3 to evaluate an expression to see whether it is divisible by 3 is the same as evaluating whether it =* 0 mod 3. Where only addition, subtraction or multiplication are involved, we can simplified an expression mod n by adding or subtracting n as many times as appropriate. Thus 2*(3t+1)^2+1 =* 2*(3t - 3t +1)^2+1 =2* 1^2+1 =* 0 mod 3 and 2*(3t +2)^2+1 =* 2*(3t-3t-3 +2)+1 = 2*(-1)^2 +1=* 0 mod 3, Thus 2n^2 + 1 =* 0 mod 3 when ever n is not 0 mod 3.

**Almutairi** · Apr6-09, 08:49 AM

Thank you for the confidence boost, and also thanks for the mod operator info it really helped. Unfortunately, every one who knows me will count this as a life achievement

.

**ramsey2879** · Apr6-09, 10:46 AM

Originally Posted by Almutairi

Thank you for the confidence boost, and also thanks for the mod operator info it really helped. Unfortunately, every one who knows me will count this as a life achievement.

Unfortunately, ones ego is often set even before preschool. Because of the programing you under go in your early years one's subconcious mind often works to sabotage ones efforts to succeed. It never matters what others believe you are capable of if you yourself work subconciously to prove yourself to not have the talent. You most likely have the talent but do not know it. Your work shows that you have talent in math. If I were you, I would never base my goals purely on others or even your own concepts about your talent. If you believe in your self you will succeed in math. I can see that from what you done. My advice is to for you continue to post more of your work or questions in this forum. Give it your best, you may surprise yourself!