| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Proposed by J. C. Binz, University of Bern, Bern, Switzerland.
Find all positive integers m such that
M[n] = { C(1,2), C(2,2), C(3,2), ..., C(n,2) }
is a complete set of residues module n.
[C(m,n) is the number of ways to choose n things from m.]
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1766.1 | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Tue Jun 15 1993 00:31 | 3 | |
Computer trials suggest an interesting pattern. :-)
Dan
| |||||
| 1766.2 | Observations | CADSYS::COOPER | Topher Cooper | Tue Jun 15 1993 17:24 | 3 |
First observation -- these are the triangular numbers up to n.
Topher
| |||||
| 1766.3 | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Fri Jun 18 1993 00:24 | 5 | |
The only such n for 2 <= n <= 1000 are
{ 2, 4, 8, 16, 32, 64, 128, 256, 512 }
Dan
| |||||
| 1766.4 | RUSURE::EDP | Always mount a scratch monkey. | Mon Jun 06 1994 17:15 | 21 | |
Solution by David Hankin, John Dewey High School, New York.
The elements of M[n] will be a complete set of residues if, and only
if, [there are no solutions to]
C(x,2) is congruent to C(y,2) modulo n, 1 <= x < y <= n.
We will show this is the case if, and only if, n is a power of 2.
First, note that C(x,2) is congruent to C(y,2) modulo n if, and only
if, (y-x)(y+x-1) is congruent to 0 modulo 2n.
Suppose n is a power of 2; then so is 2n. Since y-x and y+x-1 are of
different parity and both are less than 2n, it is clear that 2n cannot
divide their product. Thus, M[n] must be a complete set of residues
modulo n.
Suppose n is not a power of 2, and write n = 2^e*m, where m is odd, m
>= 3 and e >= 0. Set y-x = min{2^(e+1),m} and y+x-1 = max{2^(e+1),m}.
Then y = (2^(e+1)+m+1)/2 and x = (abs(2^(e+1)-m)+1)/2. Then 1 <= x < y
<= n and from above, C(x,2) is congruent to C(y,2) modulo n.
| |||||