My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 27th, 2012, 10:29 AM   #11
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: (Failed) Proof: There are no odd Giuga numbers

Thanks, I'll mess around a bit more with it in case I get anywhere, but will check a bit more carefully before posting again.
Hedge is offline  
 
January 13th, 2013, 09:26 AM   #12
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: (Failed) Proof: There are no odd Giuga numbers

This is a more complex version than I tried before so grateful for any comments. I can't see a problem now, so it might work, though if there is one it could be with the use of "modular fractions".

(C.R.Greathouse - it's the same as before up to IV, which you had verified up to - after that it is different.)

Proof: There are no odd Giuga numbers
Assume X is a Giuga number, meaning that for any of its prime factors p
X/p – 1 = 0 mod p

The factors of X are a<b<c<d<e<f….
C = cdefghi….. (in other words the product of all of X’s factors other than a and b)

I. aC = abC/b = 1 mod b
II. bC = abC/a = 1 mod a

using a number residue system where the co-ordinates are (a,b,c,d,e,f.....)
aC = (0,1,0,0,0,0….)
bC = (1,0,0,0,0,0….)
abdefgh…. = (0,0,1,0,0,0,0,….)
abcefgh… = (0,0,0,1,0,0,0….)
and so on, therefore

aC+bC+ abdefgh… + abcefgh… etc = aC + bC + abY = (1,1,1,1,1,1,1….)
(where Y = defgh… + cefgh…. etc, for instance for a five factor number Y = cd + ce + de and C = cde)

(1,1,1,1,1,1,1….) = 1 mod abC

III. aC + bC + abY = 1 mod abC
Therefore:

IV. aC + bC = (a+b)C = 1 mod ab
V. abY = 1 mod C

Therefore abY-1= KC where K is either 1 or an integer > 1 coprime to abY.
C = (abY-1)/K

First we need to look at the case where K = 1, then we can move on to K > 1

VI.
Assume K = 1
C = abY - 1
Therefore
C = -1 mod b

aC = 1 mod b (From I)
C = - 1 mod b (From above)
aC + C = 0 mod b = 0 mod C

(This must be bC because (a+1)C can't be a higher multiple of b than bC)

aC + C = bC
a + 1 = b

Therefore a = 2, b = 3
(Because these are the only primes which are separated by 1).

VII.

Next, we need to check what can happen if K >1. For this I need to use what I'll call a "modular fraction". (Not sure if there is better notation for this technique).

VIII.
C = (abY - 1)/K = -1/K mod ab/K

I need to explain how I am using the modular fraction -1/K mod ab/K, and how multiplication and addition of these fractions works.

IX.

i. If a number is -1/K mod ab I mean that it is 1/K less than a multiple of ab/K (not 1/K less than a multiple of a)

For instance if 15 = (2x7) + 1 = 1 mod 7 then 7 = -1/2 mod 15/2. Thus 7 = - 1/2 mod 15/2 , 14 = -2/2 mod ab/K= -1 mod ab/K , 21 = - 3/2 mod ab/K and so on.

ii. If -1/K mod ab/K is an integer, then a multiple of that integer that is (a multiple of a) mod ab/K must be 0 mod a
By the same token, a multiple of that integer that is (a multiple of b) mod ab/K must be 0 mod b
This is because a, b and K are coprime, so an a or b in the numerator can't be cancelled out by an a or b in the denominator. For instance (3 x 7) = -3/2 mod 15/2 = 0 mod 3, and (5 x 7) = - 5/2 mod 15/2 = 0 mod 5

iii. A multiple of -1/K mod ab/K that is not a multiple of a mod ab/K can't be 0 mod a because there is no a in the numerator. For instance, to calculate the lowest actual value of - n/K mod ab/K we multiply n by ab/K then subtract n/k = (abn - n)/K. For instance 21 = -3/2 mod 15/2 = (45- 3)/2). If the numerator of this equation isn't 0 mod a then its actual value can't be 0 mod a.

(One more way of putting this - if we start at an integer -1/K mod ab/K then go up through the values -2/K, - 3/K....-a/K etc mod ab/K, only the multiples of a/K will relate to an integer that is 0 mod a - some of the rules above can't be generalised to "any -n/K mod ab/K but they do work for "an integer which is -1/K mod ab/K and multiples of that integer")

iv. When n/K is a whole number N then N mod ab/K = N mod ab (for instance 2 x 7 = - 2/2 mod 15/2 = -1 mod 15/2 = -1 mod 15. However, if n/K isn't a whole number, then n/K mod ab/k isn't equal to n/K mod ab (for instance 1 x 7 = -1/2 mod 15/2 but = 7 mod 15.

v. To add 1 to n/K mod ab/K we have to add K to the numerator. For instance:
(3 x 7) = 21 = -3/2 mod 15/2
(3 x 7) + 1 = 22 = -1/2 mod 15/2

And another example
28 = - 4/2 mod 15/2
29 = -2/2 mod 15/2 = -1 mod 15

vi. If a number is n/K mod ab/K it is also n/K mod a/K and n/K mod b/K.
For instance 49 = -7/2 mod 15/2 = -7/2 mod 3/2 = - 7/2 mod 5/2
This is 7/2 less than 105/2 = 0 mod 15/2 = 0 mod 3/2 = 0 mod 5/2.

Using these rules:

If K > 1

From VIII.
C = -1/K mod ab/K
aC = -a/K mod ab/K
aC - 1 = (-a-K)/K mod ab/K = (-a-K)/K mod b/K (from IX vi.)
aC - 1 = 0 mod b (from I.)
(-a-K)/K mod b/K = 0 mod b

(-a-K) = 0 mod b (from IX. ii)

Therefore

X.
a+K = 0 mod b

Also

From VIII.
C = -1/K mod ab/K
bC = -b/K mod ab/K
bC - 1 = (-b-K)/K mod ab/K = (-b-K)/K mod a/K (from IX vi.)
bC - 1 = 0 mod a (from II.)
(-b-K)/K mod a/K = 0 mod a

XI.
(-b-K) = 0 mod a (from IX. ii)

Therefore

XII.
b + K = 0 mod a (from XI.)

XIII.
Using a number residue system where the co-ordinates are (a,b)

a = - K mod b = (0, -K) (From X.)
b = - K mod a = (-K, 0) (From XII.)
K = K mod a, K mod b = (K, K) (by definition - the actual residue may be lower than K but it will be congruent to K)
b + K = (0, K)

This must be either (a + 2K) or (a + 2K + Zab) (where Zab is a multiple of ab)

This can only be 0 mod a if 2K = 0 mod a (because, if 2K = 0 mod a then 2K +Zab is also 0 mod a)

K is coprime with a so this is only possible if a = 2

Therefore there are no odd Giuga numbers.

nb: if this is correct it completes a proof of the Giuga conjecture, since that can be restated as "It is impossible for a number to be both a Carmichael number and a Giuga number", and Carmichael numbers have to be odd.
Hedge is offline  
January 14th, 2013, 05:23 AM   #13
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: (Failed) Proof: There are no odd Giuga numbers

incidentally, the rules for the fraction -1/K mod ab/K are specific to that fraction (where a,b and K are coprime and -1?K mod ab/K is an integer).

The same rules can't be generalised to any integer described as n/K mod ab/K. For instance 35 = 5/2 mod 7/2. However you can't divide this by 5 and find an integer 1/2 mod 7/2, so the rules for addition and multiplication work a bit differently.
Hedge is offline  
January 14th, 2013, 08:09 AM   #14
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: (Failed) Proof: There are no odd Giuga numbers

Just working on an alternative version that doesn't rely on those pesky modular fractions so you don't have to look at all those rules for how they work - it's actually the same logic (if it works, that is), but spelled out in a different way.

Will come back shortly.
Hedge is offline  
January 14th, 2013, 12:30 PM   #15
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Re: (Failed) Proof: There are no odd Giuga numbers

Ah, and that means I see the flaw...

Only a frustrating little one, but a bit on the fatal side.
Hedge is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
failed, giuga, numbers, odd, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proof of Fib's numbers. FreaKariDunk Number Theory 3 February 11th, 2012 10:02 AM
Algebraic Numbers Proof julian21 Number Theory 5 October 16th, 2011 01:20 PM
Fibonacci Numbers Proof jstarks4444 Number Theory 1 October 12th, 2011 05:37 PM
Proof of m > n in the Natural Numbers jstarks4444 Number Theory 4 February 18th, 2011 05:22 PM
Proof of real numbers Tartarus Algebra 4 November 27th, 2009 02:56 AM





Copyright © 2019 My Math Forum. All rights reserved.