odd numbers
 

A nice simple problem

[tex]x_{i}[/tex] odd integers, [tex]n>2[/tex]

To prove:
[tex]4|(\prod_{i=1}^{n}x_{i }x_{i+1})-n[/tex], where [tex]x_{n+1}=x_1 [/tex]

Kees,

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

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

Ah, I see the typo, sorry

it should be
[tex] 4|(\sum_{i=1}^{n}x_{i }x_{i+1})-n,\ \mathrm{where}\qquad x_{n+1}=x_1 [/tex]

That appears to be the same expression as before.

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

The PI for multiplication was changed to a SIGMA for addition.
And I believe it's true for n > 1, not just n > 2.

Every odd number is congruent to either 1 or 3 (mod 4).
A product x[sub]i[/sub]x[sub]i+1[/sub] is congruent to 1 (mod 4) if
both x[sub]i[/sub] and x[sub]i+1[/sub] 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[sub]1[/sub]x[sub]2[/sub] - 1) + (x[sub]2[/sub]x[sub]3[/sub] - 1) + ... + (x[sub]n[/sub]x[sub]n+1[/sub] - 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[sub]i[/sub] as i progresses from
1 to n+1. This must be even since the last x[sub]n+1[/sub] = x[sub]1[/sub].

[quote=davar55;104669]The PI for multiplication was changed to a SIGMA for addition.
[/quote]
Or "Crooked E" as Jasong decribed it:smile:

[quote=davar55;104673]Every odd number is congruent to either 1 or 3 (mod 4).
A product x[sub]i[/sub]x[sub]i+1[/sub] is congruent to 1 (mod 4) if
both x[sub]i[/sub] and x[sub]i+1[/sub] have the same 1 or 3 parity
and is congruent to 3 (mod 4) if they have different 1 or 3 parity.

[/quote]

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

Induction?
 

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

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