- This is an interesting example of how small numbers don't always

behave the same as big numbers, and it's somewhat related to prime

numbers (well, factorization anyway)...

Start enumerating those values of sigma(N) which are divisible by 17

(sigma function here being the sum of positive integer divisors).

The first few are of course:

sigma(67) == 68

sigma(101) == 102

sigma(128) == 255

sigma(134) == 204

There seems to be no scarcity of such numbers -- for N < 10^6, we

have sigma(N) divisible by 17 a grand total of 80608 times,

a hit rate of just over 8%.

Now also enumerate those values of sigma(N) which are congruent

to 5 (modulo 6):

sigma(2401) == 2801

sigma(9604) == 19607

sigma(21609) == 36413

sigma(28561) == 30941

Okay, these are a little bit scarce, but still, there are 24

of them for N < 10^6, and 1644 of them for N < 10^10. There

are clearly an infinite number of them -- for instance, given

any prime p of the form 6*a+1, N = p^4 will work.

The big question is, how far do you have to go to find a number

which is in both lists?

Or for those who like their problem stated succinctly:

What is the smallest N such that sigma(N) is congruent to

17 (modulo 102)?

Jack - --- jbrennen <jb@...> wrote:
> What is the smallest N such that sigma(N) is congruent to

Well, an upper bound is 160470643909878751793805444097921

> 17 (modulo 102)?

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign

/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________

Do You Yahoo!?

Tired of spam? Yahoo! Mail has the best spam protection around

http://mail.yahoo.com - Apologies if people get 2 copies - yahoo seems flakey, so I'm trying

again.

--- In primenumbers@yahoogroups.com, "jbrennen" <jb@...> wrote:

> What is the smallest N such that sigma(N) is congruent to

> 17 (modulo 102)?

An upper bound is 160470643909878751793805444097921

Phil - I think you can prove that Phil's example 103^16 is the smallest

such number. Sigma(n) has factors (1+p+p^2+...+p^k) for p^k||n (<-

largest power of p that divides n). For sigma(n) to be 5 mod 6, all

the factors have to be either 1 or 5 mod 6 (i.e., no factors that

are 2,3,4,0 mod 6). By examination, for p=2 and p=3,

(1+p+p^2+...+p^k) is never 0 mod 17 and 1 or 5 mod 6.

For p=3, we get 1+3+3^2+...+3^k odd when k is even but then

1+3+3^2+...+3^k=(3^(k+1)-1)/2 while the order of 3 mod 17 is 16 so 3^

(k+1)-1 is divisible by 17 only when 16 divides k+1. It can not be

true that k is even and 16 divides k+1.

For p=2, we get 1+2+2^2+...+2^k is 1 mod 3 when k is even. But the

order of 2 mod 17 is 8, so 2^(k+1)-1 == 0 mod 17 means (k+1) is even.

The only other available primes are either 1 or 5 mod 6. If p is 5

mod 6 and 1+p+...+p^k is either 1 or 5 mod 6, then k is even. If p

is 1 mod 6 and 1+p+...+p^k is either 1 or 5 mod 6, then k is either

4 or 6 mod 6.

For k even, solve 1+x+...+x^k==0 mod 17 and find the first solution

happens when k=16 and x==1 mod 17. The first prime that is 1 mod 17

is 103. 103^16 is the first number that solve sigma(n)==17 mod 102. - --- In primenumbers@yahoogroups.com, "Adam" <a_math_guy@...> wrote:
>

Yes, and you seemed to give a convincing argument. :)

> I think you can prove that Phil's example 103^16 is the smallest

> such number.

Did anyone notice that I basically gave away the key to finding

Phil's example? I stated that solving sigma(N) == 5 (mod 6)

was easily done by picking a prime p of the form 6*x+1 and

then taking p^4, or p^(5-1).

This is of course easily generalized...

So to solve sigma(N) == 17 (mod 102), find a prime of the

form 102*x+1. The first such is of course 103. And then

set N = 103^(17-1) = 103^16.

The tricky part is proving that 103^16 is in fact the minimal

solution.

My method for doing so:

Note that N must be divisible by a prime power p^a which

has sigma(p^a) divisible by 17 but not divisible by 2 or 3.

Note also that sigma(p^a) = (p^(a+1)-1)/(p-1).

In order for sigma(p^a) to be an odd number (not divisible

by 2), we need to have either p or a be even.

If p is even, it must be 2, and we would have:

p^(a+1) == 1 (mod 17). It turns out that this is true

when a == 7 (mod 8); however, when a == 7 (mod 8), we

also have sigma(2^a) divisible by 3. So that doesn't

work.

So p must be odd and a must be even. In order for

p^(a+1)-1 (the numerator of the expression above) to

be divisible by 17, (a+1) must be divisible by the

order of p modulo 17. Note that the order of p

modulo 17 must divide evenly into 16 (a consequence

of Fermat's Little Theorem). So we have an

odd number (a+1) which must be divisible by a

divisor of 16. Clearly the divisor (the order of

p modulo 17) must be 1. This implies that the

prime p is in fact of the form 17*x+1.

And once we know that p == 1 (mod 17), we can see

easily that a must be of the form 17*y-1.

The smallest prime p of the form 17*x+1 is 103,

and the smallest exponent a of the form 17*y-1 is 16.

So the smallest prime power which has sigma(p^a)

divisible by 17, but not by 2 or 3, is 103^16.

So any solution N to the original puzzle must be

divisible by a prime power >= 103^16.

There are not a lot of ordered pairs (A,B) such

that A > 2 and such that N = (B+1)^(A-1) is the

smallest solution to sigma(N) == A (modulo B).

I know of these three: (5,6), (5,30), and (17,102).

There could be others, if anyone wants to try

to find them. It's interesting that for those

three I know of, A is always a Fermat prime.