
#1
Apr409, 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 



#2
Apr409, 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... 



#3
Apr409, 10:47 AM

Sci Advisor
HW Helper
Thanks
P: 26,167

Hi Almutairi! Welcome to PF!
(try using the X^{2} tag just above the Reply box ) Generally, 2^{2n}  1 = 4^{n}  1 is divisible by 3, and so is 2^{2n+1} + 1, as you can see by writing 4 in ternary (ie, it's "11" in base3). 



#4
Apr409, 10:54 AM

P: 223

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



#5
Apr509, 03:37 AM

P: 6

let n=7( seven is not zero and not divisible by 3) so (7^{2})*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^{2}+1] is Always a multiple of 3 2) if n is an integer divisible by 3 and not equal to zero then [2n^{2}+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})/3 + (n^{2})/2 + n/6 is always an integer, but as I said it was long, I will post it later. 



#6
Apr509, 03:41 AM

P: 6





#7
Apr509, 04:16 AM

Sci Advisor
HW Helper
Thanks
P: 26,167

if it ends in 1 or 2, then n^{2} ends in 1 



#8
Apr509, 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 ? 



#9
Apr509, 04:10 PM

P: 1,133

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



#10
Apr509, 07:43 PM

P: 6

Proof
Given that [(n^{3})/3 + (n^{2})/2 + n/6] is an integer, then [ 2n^{3} + 3n^{2}+ n] is an integer that is a multiple of 6 and therefore, [2n^{3}+ n] is a multiple of 3 and it can be written as n[2n^{3} + 1] so either n or [2n^{2} + 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^{2} + 1] be multiples of 3, then 2n^{2} is NEVER a multiple of 3 ...(A) However, by a counter example we can show this is not true (e.g. 2*3^{2}=18), so either it is sometimes true or always true. For obvious reasons it cant be sometimes true and sometimes not true, so 2n^{2} is always a multiple of 3 . (B) Statements A and B are clearly in contradiction. so either n or [2n^{2} + 1] is a multiple of 3. 



#11
Apr509, 09:50 PM

P: 891





#12
Apr609, 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.




#13
Apr609, 09:46 AM

P: 891




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  
(n1)! is divisible by n  Linear & Abstract Algebra  7  
Prove that phi(a^n  1) is divisible by n  Linear & Abstract Algebra  7 