2010-03-31

Math Proofs : Need Help

Every day I walk the dog a couple of miles to get her and me some fresh air and exercise.. it is usually the same route, meeting the same people, etc etc.. so I come up with things to keep my head busy. Sometimes its remembering as many elements and their isotopes, other times working out factors of numbers. Last week I started on the series (n^2+1) to see what their factors were. The first thing I realized was that while half of the numbers would be divisible by 2, around 40% would be divisible by 5 (because any number ending in 2,3,7,8 would square to a number that adding 1 would make it divisible by 5 (eg 13^2+1 = 169+1 = 170). Then after a lot of ticking off things I also realized that none of the numbers I could do (which isn't a lot .. I do this because math and me have a long bad history) were not divisible by 3.

Coming home I whipped up a python scriplet that basically did that for the first million digits and found that none of them were divisible by 3 (they weren't divisible by 7 either but I figured I would stick with 3 first). Now we know that n^2 is sometimes divisible by 3 (9, 36, 81 all being examples) and we know that a series that is always divisible by 3 is 3m (two series never divisible by three are 3m+1 and 3m+2). So from this I infer that the series n^2+1 only falls inside of the series 3m+1 and 3m+2 and never on 3m... and n^2 falls on 3m or 3m+1 (since if it fell on 3m+2 then n^2+1 would push those values to 3m). Ok but why?

Looking over the series I came up with the following:


n 1 2 3 4 5 6 7 8 9 10
n^2 1 4 9 16 25 36 49 64 81 100
m{3m+1/3m} 0 1 3 5 8 12 16 21 27 33
diff between m 1 2 2 3 4 4 5 6 6



Ok now I just have more silly numbers and probably a wild goose chase but it is interesting that the series of 3m/3m+1 growth grows in a regular pattern. Anyway, just an odd thing non-fedora related (i hope).

6 comments:

Matthias said...

n^2 + 1 = 3m would mean that 2 is a quadratic residue mod 3. But there are only (p - 1)/2 quadratic residues for an odd prime modulus. For 3, the sole quadratic residue is 1...

To see why, look at the field Z/pZ. The squares 1^2, 2^2,..., (p-1)/2 ^2 enumerate all the quadratic residues mod p. They are all different, since x^2 = y^2 implies (x + y)(x - y) = 0, ie x must be y or -y.

Miloslav said...

The fact that (n^2+1) is never divisible by 3 can be proven like this:

Two small reminders:
* "X is divisible by 3" <=> X % 3 == 0 (using the C notation)
* (A * B) % 3 == (((A % 3) * (B % 3)) % 3)

Therefore, (n^2)%3 == ((n%3)^2)%3, and we have three cases to consider:
* n%3 == 0, then (n^2)%3 == 0
* n%3 == 1, then (n^2)%3 == 1
* n%3 == 2, then (n^2)%3 == 4%3 == 1

We see that (n^2)%3 != 2, therefore (n^2+1)%3 != 0, hence (n^2+1) is never divisible by 3.

As for "diff between m", start with differences between n^2:
* (n+1)^2 == n^2 + (2n+1)

Your "diff between m" is thus (2n+1)/3, except for rounding. Similarly to the above, you can determine the structure of (2n+1)%3. Looking at this will reveal the reason why two out of three values are repeated, details left as an exercise :)

Jef Spaleta said...

Its all about the modulus of 3 and the quadratic equation.

Take n=a*3+b where a is any integer
take b as 0, 1 or 2

Now n^2=9*a^2+6*a*b+b^2=3*C+b^2

b^2 is either 0, 1, 4
4=3+1

when b=0 n^2=3c
when b=1 n^2=3c+1
when b=2 n^2=3c+1

Now m=n^2+1=3*c+b^2+1
when b=0 n^2+1=3c+1
when b=1 n^2+1=3c+2
when b=2 n^2+1=3c+2

DDD said...

Hi,

You have discovered modulo arithmetic :)

Basically you are saying n^2 +1 != 0 mod 3

You can just try this for small values of n:
n = 0 value = 0*0+1 = 1
n = 1 value = 1*1+1 = 2
n = 2 value = 2*2+1 = 5 = 2 mod 3

The secret is any polynomial will also repeat with n mod 3. This is because you can rewrite n' as (n + 3a) where a is an integer.

Substitute this into your original equation:
(n + 3a)^2 + 1 mod 3
becomes:
n^2 + 2 * 3a + 3a * 3a + 1 mod 3
becomes:
n^2 + 3*(2a + 3a) + 1 mod 3
But mod 3 the second term is 0. So:
n^2 + 1 mod 3

Hence the repeating 1 2 2 results for n mod 3

Regards,

DDD

P.S The maths was way easier than logging into this comments system :)

Charlie said...

The difference between two squares is always 2n+1. Since we are just looking at how far from a multiplier by 3 we are we can just mod 3 the numbers. This gives a pattern of 0,2,1,0,2,1,0,2,1...

A number 0 (an increase by a multiplier of 3) says the next number will have the same offset as the last. A number of 1 says the offset will increase by 1. And a value of 2 says the offset will decrease by one.

So 0, -1, +1, 0, -1, +1.... will be stuck dithering back and forth between the two places.

The mod 5 of the sequence (0, 2, 4, 1, 3, 0, 2...) is interesting because it happens to a mod 5 number (as 0+2+4+1+3=10) just before getting the next zero, thus spending two turns at zero and explaining why two of the five numbers in the sequence are divisible by five.

Smooge said...

Thanks guys. I appreciate the help.