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


by Almutairi
Tags: divisible
Almutairi
Almutairi is offline
#1
Apr4-09, 10:26 AM
P: 6
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
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
signerror
signerror is offline
#2
Apr4-09, 10:36 AM
P: 223
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
tiny-tim is offline
#3
Apr4-09, 10:47 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Hi Almutairi! Welcome to PF!

(try using the X2 tag just above the Reply box )
Quote Quote by Almutairi View Post
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(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).

signerror
signerror is offline
#4
Apr4-09, 10:54 AM
P: 223

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


Quote Quote by tiny-tim View Post
Sorry, but 2(22) + 1 = 16 + 1 = 17
[tex]2\cdot n^2 \mbox{, not } 2^{n^2}[/tex]
Almutairi
Almutairi is offline
#5
Apr5-09, 03:37 AM
P: 6
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 2n2, 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 (72)*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 [2n2+1] is Always a multiple of 3

2) if n is an integer divisible by 3 and not equal to zero then [2n2+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 (n3)/3 + (n2)/2 + n/6 is always an integer, but as I said it was long, I will post it later.
Almutairi
Almutairi is offline
#6
Apr5-09, 03:41 AM
P: 6
Quote Quote by signerror View Post
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...
I am sorry I didn't understand what you were trying to do could you please explain it differently.
tiny-tim
tiny-tim is offline
#7
Apr5-09, 04:16 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by Almutairi View Post
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 n2 ends in 1
dextercioby
dextercioby is offline
#8
Apr5-09, 07:44 AM
Sci Advisor
HW Helper
P: 11,863
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
Gear300 is offline
#9
Apr5-09, 04:10 PM
P: 1,133
You could prove it with less paper (supposedly) by using
1 = 12
1 + 3 = 22
1 + 3 + 5 = 32
1 + 3 + 5 + 7 = 42...and so forth with this pattern
Almutairi
Almutairi is offline
#10
Apr5-09, 07:43 PM
P: 6
Proof

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

[ 2n3 + 3n2+ n] is an integer that is a multiple of 6

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

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

so either n or [2n2 + 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 [2n2 + 1] be multiples of 3,

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

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

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

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

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

Statements A and B are clearly in contradiction.

so either n or [2n2 + 1] is a multiple of 3.
ramsey2879
ramsey2879 is offline
#11
Apr5-09, 09:50 PM
P: 891
Quote Quote by Almutairi View Post
Proof

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

[ 2n3 + 3n2+ n] is an integer that is a multiple of 6

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

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

so either n or [2n2 + 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 [2n2 + 1] be multiples of 3,

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

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

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

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

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

Statements A and B are clearly in contradiction.

so either n or [2n2 + 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
Almutairi is offline
#12
Apr6-09, 07:49 AM
P: 6
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
ramsey2879 is offline
#13
Apr6-09, 09:46 AM
P: 891
Quote Quote by Almutairi View Post
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!


Register to reply

Related Discussions
infinitely divisible vs finitely divisible time General Physics 8
Numbers divisible by 3 Precalculus Mathematics Homework 8
Divisible by a square Linear & Abstract Algebra 27
(n-1)! is divisible by n Linear & Abstract Algebra 7
Prove that phi(a^n - 1) is divisible by n Linear & Abstract Algebra 7