All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Proving divisibility (Posted on 2017-01-08) Difficulty: 2 of 5
Given two integers n (n>1) and an odd prime p. Without loss of generality let p=2k-1.

Prove that if C(n,2) - C(k,2) is divisible by p, it must be divisible also by p2.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
proof Comment 2 of 2 |

let F(n,k)=C(n,2)-C(k,2)=n(n-1)/2-k(k-1)/2=n(n-1)/2-(p+1)(p-1)/4
so now let G(n,p)=(2n^2-2n-p^2+1)/4

if G(n,p)=0 mod p then we have
(2n^2-2n-p^2+1)/4=0 mod p
since p is odd, 4 has a multiplicitve inverse and thus can be canceled out
2n^2-2n-p^2+1=0 mod p (1)
2n^2-2n+1=0 mod p

now let G(n,p)=r mod p^2
and let 4 have a multiplicative inverse of i
then we get
2n^2-2n-p^2+1=ir mod p^2
2n^2-2n+1=ir mod p^2
from (1) above we now get
0=ir mod p^2
now since the multiplicative inverse of 4 can't be 0 we are left with
r=0 mod p^2

thus G(n,p)=0 mod p^2

thus if C(n,2)-C(k,2) is divisible by p, then it is also divisible by p^2

  Posted by Daniel on 2017-01-09 07:42:29
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information