Let integers m, n satisfy . Prove that m is a multiple of 2003.(This problem of course should have been posted 3 years ago...)

- alexandreC
**Posts:**678**Joined:**

m = 187280139691754991954689696064673719711956788730199355005674805517848644623283\575956589582972941220749058108870240015721647317682809494503732310130055648879\961606413551481551869453347108706902962755469906099131479501769095352735649581\434239212808088032702745003389952703510255438779039702464445167161742840942360\397072142186643221015050354899119482884234567477313020919158418766023013624153\052523781373052284463525342140321762861105335532913216523556739076565249604889\383299681215658737890725382784817644276785987211068931426756143567708362506258\690797803421251146398466511266510214481m / 2003 = 934998201157039400672439820592479878741671436496252396433723442425604815892579\011266048841602302649770634592462506319129542275001545154786481827908415620968\355498819528115585968314264147313544497031801827754026357971887645295734645938\263800363495197367462531220119584141339268291458011495079606426169460014689767\334359172174953674563406664498849140710107675872755970639832345312146847848991\774956472157025883492388128508845545986546857378498335115111028839566897677930\021466206768141477237770258536283795690394344538536851855996722754410197235440\29354869406515799499983280712186827, integer, QED.

Last edited by alexandreC on April 22nd, 2006, 10:00 pm, edited 1 time in total.

There is a nice theorem about divisibility of numerator of alternating harmonic sum.2003 is a prime p=6k-1 (k=334), then p divides a(4k-1)=a(1335).Ref: http://www.research.att.com/~njas/sequences/A097279

Last edited by Chukchi on April 23rd, 2006, 10:00 pm, edited 1 time in total.

Yes, it is the same statement. Still no proof though...

- zarnywhoop
**Posts:**337**Joined:**

What's wrong with the given proof? I guess one should show that the suggested numerator and denominator are coprime, but there's not much else to do.

QuoteOriginally posted by: zarnywhoopWhat's wrong with the given proof? I guess one should show that the suggested numerator and denominator are coprime, but there's not much else to do.Could there possibly be a bug in the given "proof"?In any case, the real problem is of course to find a proof that would also stand for any prime p = 6k-1, as Chukchi pointed out below.

- mattcushman
**Posts:**100**Joined:**

2003 is prime. Multiply numerator and denominator by 2003!, you get that the denominator is not divisible by 2003, and the numerator is a sum of terms of the form (-1)^k 2003!/k, where k<=1335. All of these terms are divisible by 2003, hence the numerator is divisible by 2003. QED.

QuoteOriginally posted by: mattcushman2003 is prime. Multiply numerator and denominator by 2003!, you get that the denominator is not divisible by 2003, and the numerator is a sum of terms of the form (-1)^k 2003!/k, where k<=1335. All of these terms are divisible by 2003, hence the numerator is divisible by 2003. QED.Why the denominator is not divisible by 2003?Wouldn't this argument hold for any other prime imaginable? Or any other bound (besides 1335), for that matter? P.S. Sorry, crossed with your later post...

Last edited by sevvost on April 23rd, 2006, 10:00 pm, edited 1 time in total.

- mattcushman
**Posts:**100**Joined:**

Nevermind.. just realized my "proof" is erroneous. Needs more work on the numerator...

- wannabequantie
**Posts:**70**Joined:**

Hi,Heres a solution to the problem. In what follows i'm going to be working in the field , so when i write a = b i mean of course a=b modulo(2003) and when i write 1/a I mean the inverse of a in this field F. Now note that 1 + 1/2 + 1/3 + ... 1/2002 = 0 since this is the same as the set of numbers 1, 2, 3 ... 2002 under some permutation. Also 1/(2003-a) = -1/a. Now let A = 1 - 1/2 + 1/3 ... 1/1335 = (1-1/2+1/3...1/1335) + (1+1/2+1/3+...1/2002)= 2(1 + 1/3 + 1/5 +... 1/1335) + (1/1336 + ... 1/2002)= 2(1 + 1/3 + 1/5 +... 1/1335) - (1/667 + ... 1)= 2(1 + 1/3 + 1/5 + ...1/1335) - 2(1/2 + 1/4 + ...1/1334)= 2(1 - 1/2 + 1/3 - 1/4 ... 1/1335) = 2A.So now since we have A = 2A therefore A has to be equal to zero! QED.I have left some details to be filled but i assume anyone reading this should be able to fill that in.Ofcourse note that this method is quite general and you can use the same proof for any prime of the form 3n - 1 instead of 2003.

Dear wannabequantie,very nice proof!!! Awesome!!!BTW, are you one of those who came to quant with a Math Ph.D.?

Yes, this is correct. Here is a "naive" version of the same solution.m/n = 1 -1/2 + 1/3 - ...- 1/1334 + 1/1335 = (1 + 1/2 + 1/3 +...+ 1/1334 + 1/1335) - 2(1/2 + 1/4 + ... + 1/1334) = 1/668 + 1/669 + ... + 1/1335.Now, grouping terms in pairs in a school kid Gauss manner (conveniently, we have an even number of terms), we have:m/n = (1/668 + 1/1335) + (1/669 + 1/1334) + ... + (1/1001 + 1/1002) and the result follows from each term being equal 2003/q where q = k(2003-k) is relatively prime to 2003.

GZIP: On