odd numbers

Kees · 2007-04-26, 09:47

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$

Wacky · 2007-04-26, 12:28

Kees,

I don't think that this is true unless n = 1 mod 4.

Kees · 2007-04-26, 12:33

Perhaps I made a typo, but could you please give me a counterexample

Kees · 2007-04-26, 12:36

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$

Wacky · 2007-04-26, 15:50

That appears to be the same expression as before.

Rather than … -n, don't you want … -1 ?

davar55 · 2007-04-26, 18:53

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 · 2007-04-26, 19:24

Every odd number is congruent to either 1 or 3 (mod 4).
A product x_ix_i+1 is congruent to 1 (mod 4) if
both x_i and x_i+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
(x₁x₂ - 1) + (x₂x₃ - 1) + ... + (x_nx_n+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 x_i as i progresses from
1 to n+1. This must be even since the last x_n+1 = x₁.

davieddy · 2007-04-27, 11:18

Quote:

Originally Posted by davar55

The PI for multiplication was changed to a SIGMA for addition.

Or "Crooked E" as Jasong decribed it

davieddy · 2007-04-28, 07:40

Quote:

Originally Posted by davar55

Every odd number is congruent to either 1 or 3 (mod 4).
A product x_ix_i+1 is congruent to 1 (mod 4) if
both x_i and x_i+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

davieddy · 2007-04-28, 08:55

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

)

davieddy · 2007-05-03, 11:04

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

2007-04-26, 09:47	#1
Kees Dec 2005 2²×7² Posts	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$

2007-04-28, 08:55	#10
davieddy "Lucan" Dec 2006 England 6474₁₀ Posts	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

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

2007-04-26, 12:28	#2
Wacky Jun 2003 The Texas Hill Country 3²×11² Posts	Kees, I don't think that this is true unless n = 1 mod 4.

2007-04-26, 12:33	#3
Kees Dec 2005 2²·7² Posts	Perhaps I made a typo, but could you please give me a counterexample

2007-04-26, 12:36	#4
Kees Dec 2005 2²·7² Posts	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$

2007-04-26, 15:50	#5
Wacky Jun 2003 The Texas Hill Country 3²·11² Posts	That appears to be the same expression as before. Rather than … -n, don't you want … -1 ?

2007-04-26, 18:53	#6
davar55 May 2004 New York City 5·7·11² Posts	The PI for multiplication was changed to a SIGMA for addition. And I believe it's true for n > 1, not just n > 2.

2007-04-26, 19:24	#7
davar55 May 2004 New York City 5×7×11² Posts	Every odd number is congruent to either 1 or 3 (mod 4). A product x_ix_i+1 is congruent to 1 (mod 4) if both x_i and x_i+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 (x₁x₂ - 1) + (x₂x₃ - 1) + ... + (x_nx_n+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 x_i as i progresses from 1 to n+1. This must be even since the last x_n+1 = x₁.

2007-05-03, 11:04	#11
davieddy "Lucan" Dec 2006 England 2·3·13·83 Posts	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