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

Almutairi

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

Two cases:

[tex]n \equiv 1 \mod 3 \Rightarrow n^2 \equiv 1 \mod 3[/tex]
[tex]n \equiv 2 \mod 3 \Rightarrow n^2 \equiv 1 \mod 3[/tex]

Either way, [itex]n^2 \equiv 1 \mbox{ mod } 3[/itex]. Now just plug this in...

tiny-tim

Hi Almutairi! Welcome to PF!

(try using the X² tag just above the Reply box )
Sorry, but 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

[tex]2\cdot n^2 \mbox{, not } 2^{n^2}[/tex]

Almutairi

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

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

tiny-tim

Write n in ternary …

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

dextercioby

What if you take the 2 possible cases

[tex] n=3p+1 [/tex] and [tex] n=3p+2 [/tex], where 'p' is arbitrary in the set of natural numbers

?

Gear300

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

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

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

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

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!