Puzzle - Law of small numbers

Expand Messages
• 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,
Message 1 of 5 , Jan 9, 2007
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
• ... Well, an upper bound is 160470643909878751793805444097921 Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail
Message 2 of 5 , Jan 10, 2007
--- jbrennen <jb@...> wrote:
> What is the smallest N such that sigma(N) is congruent to
> 17 (modulo 102)?

Well, an upper bound is 160470643909878751793805444097921

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. ... An upper bound is 160470643909878751793805444097921 Phil
Message 3 of 5 , Jan 10, 2007
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 (
Message 4 of 5 , Jan 10, 2007
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.
• ... Yes, and you seemed to give a convincing argument. :) Did anyone notice that I basically gave away the key to finding Phil s example? I stated that
Message 5 of 5 , Jan 10, 2007
>
> I think you can prove that Phil's example 103^16 is the smallest
> such number.

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

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.
Your message has been successfully submitted and would be delivered to recipients shortly.