mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-04-26, 09:47   #1
Kees
 
Kees's Avatar
 
Dec 2005

22×72 Posts
Default odd numbers

A nice simple problem

x_{i} odd integers, n>2

To prove:
4|(\prod_{i=1}^{n}x_{i }x_{i+1})-n, where x_{n+1}=x_1
Kees is offline   Reply With Quote
Old 2007-04-26, 12:28   #2
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Kees,

I don't think that this is true unless n = 1 mod 4.
Wacky is offline   Reply With Quote
Old 2007-04-26, 12:33   #3
Kees
 
Kees's Avatar
 
Dec 2005

C416 Posts
Default

Perhaps I made a typo, but could you please give me a counterexample
Kees is offline   Reply With Quote
Old 2007-04-26, 12:36   #4
Kees
 
Kees's Avatar
 
Dec 2005

22×72 Posts
Default

Ah, I see the typo, sorry

it should be
 4|(\sum_{i=1}^{n}x_{i }x_{i+1})-n,\  \mathrm{where}\qquad x_{n+1}=x_1
Kees is offline   Reply With Quote
Old 2007-04-26, 15:50   #5
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

That appears to be the same expression as before.

Rather than … -n, don't you want … -1 ?
Wacky is offline   Reply With Quote
Old 2007-04-26, 18:53   #6
davar55
 
davar55's Avatar
 
May 2004
New York City

2×32×5×47 Posts
Default

The PI for multiplication was changed to a SIGMA for addition.
And I believe it's true for n > 1, not just n > 2.
davar55 is offline   Reply With Quote
Old 2007-04-26, 19:24   #7
davar55
 
davar55's Avatar
 
May 2004
New York City

2×32×5×47 Posts
Default

Every odd number is congruent to either 1 or 3 (mod 4).
A product xixi+1 is congruent to 1 (mod 4) if
both xi and xi+1 have the same 1 or 3 parity
and is congruent to 3 (mod 4) if they have different 1 or 3 parity.

But the given sum equals
(x1x2 - 1) + (x2x3 - 1) + ... + (xnxn+1 - 1).
So the terms of this sum are congruent to 0 or 2 (mod 4).

If there are an even number 2k of such terms congruent to 2 (mod 4),
then the sum will be congruent to 0 + 2*2k = 4k (mod 4), i.e 0 (mod 4).

But this must be true, since we just need to consider the number
of changes of 1 or 3 parity of the xi as i progresses from
1 to n+1. This must be even since the last xn+1 = x1.
davar55 is offline   Reply With Quote
Old 2007-04-27, 11:18   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by davar55 View Post
The PI for multiplication was changed to a SIGMA for addition.
Or "Crooked E" as Jasong decribed it
davieddy is offline   Reply With Quote
Old 2007-04-28, 07:40   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

145128 Posts
Default

Quote:
Originally Posted by davar55 View Post
Every odd number is congruent to either 1 or 3 (mod 4).
A product xixi+1 is congruent to 1 (mod 4) if
both xi and xi+1 have the same 1 or 3 parity
and is congruent to 3 (mod 4) if they have different 1 or 3 parity.
Neat proof davar.
For completeness:
(4a+1)(4b+3)=16ab+12a+4b+3 (=3 mod 4)
(4a+1)(4b+1)=16ab+4a+4b+1 (=1 mod 4)
(4a+3)(4b+3)=16ab+12a+12b+9 (=1 mod 4)

The result is true for n>0 surely.


David

Last fiddled with by davieddy on 2007-04-28 at 07:53
davieddy is offline   Reply With Quote
Old 2007-04-28, 08:55   #10
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

194A16 Posts
Default Induction?

Is the proof by induction more or less instructive?
(Said proof left to interested readers )

Last fiddled with by davieddy on 2007-04-28 at 08:56
davieddy is offline   Reply With Quote
Old 2007-05-03, 11:04   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

If this proposition is false there is a minimum
n for which it fails. Let N be this value.
Take N odd numbers. If it fails for this then we can prove
that it also fails for N-1 (Excersize for reader).

Etc

David
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carmichael numbers and Devaraj numbers devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 10:55.

Wed Sep 30 10:55:25 UTC 2020 up 20 days, 8:06, 0 users, load averages: 1.51, 1.55, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.