## Friday, 20 July 2012

### A modular problem page 2

I can go some way to generalising the proof I made for 3 factor numbers to numbers with more factors. For instance:

A number has 4 odd prime factors a < b < c < d

Assume
abc = 1 mod d = (0, 0, 0, 1)
abd = 1 mod c = (0, 0, 1, 0)
acd = 1 mod b = (0, 1, 0, 0)
bcd = 1 mod a = (1, 0, 0, 0)

abc + abd + acd +bcd = (1, 1, 1, 1)

Subtract 1

= (0, 0, 0, 0) = 0 or abcd

a >= 3, b >= 5, c >= 7, d >=11

abc =< abcd/11
abd =< abcd/7
acd =< abcd/5
bcd =< abcd/3

1/3 + 1/5 + 1/7 + 1/11 = 886/1185

abcd = 1185

Therefore (1, 1, 1, 1) ≠ abcd + 1

abc + abd + acd +bcd = 1

RAA

Therefore the initial assumption was impossible.

It looks to me as though this works up to 8-factor numbers (and would have worked for 3 factor numbers) but then stops working because 1/3 + 1/5 + .... 1/ 23+ 1/29 > 1 (29 being the 9th odd prime).
A number has 4 odd prime factors a < b < c < d
Also, if this works at all, then it works for any number with an odd number of factors, for instance for five factors:

abcd + abde + abce +abde + bcde = (1, 1, 1, 1, 1)

Subtract 1

= (0, 0, 0, 0, 0) = 0 or abcde

However abcde+1 is even, and (abcd + abde + abce +abde + bcde) is odd.

so abcde+1 ≠ (abcd + abde + abce +abde + bcde)

(Actually this last bit isn't completely sound - if abcd + abde + abce +abde + bcde = 1 mod abcde but this is a multiple of abcde rather than abcde itself, then the proof doesn't hold - but this at least extends the proof to numbers with a very large number of odd factors since it takes a long time to reach 2 in the series 1/3 + 1/5 + 1/7  + 1/11.... However this series isn't convergent, so you do eventually get to 2)

CRGreathouse also commented that

"You can extend it to 9- or even 10-factor numbers by adding finite checking. Probably too difficult for more than 9 factors if you're doing it by hand, though."
Which is correct - there would be many combinations for 9, 10 and above where the fractions didn't exceed 1, so it does work in theory for a big swathe of highly composite numbers - you just can't make it a general proof without finite checking.