1. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    04 Apr '03 08:21
    Following on from a problem set a while ago which I answered using Fermat's Little Theorem:

    Find n composite such that (a,n) = 1 => a^n-1 = 1 (mod n) for all a.

    (I don't know the answer, and my supervisor couldn't do it in the supervision at the time, saying I'm not an algebraist and looking something up in a book.)
  2. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    04 Apr '03 23:58
    Erm...flattery is the highest form of goading? It clearly cannot be even. I'll give it a serious look and then I will post (could be a few hours-don't know). It seems that n > 20, but I can't test much bigger w/ out some paper.
  3. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Apr '03 03:29
    Originally posted by Acolyte
    Following on from a problem set a while ago which I answered using Fermat's Little Theorem:

    Find n composite such that (a,n) = 1 => a^n-1 = 1 (mod n) for all a.

    (I don't know the answer, and my supervisor couldn't do it in the supervision at the time, saying I'm not an algebraist and looking something up in a book.)
    I thought about this all afternoon, and accomplished the following:

    1.I proved that such an n exists, and that there are more than one of them, but I would not wager that they are infinite in number;

    2.I found a couple of examples of such numbers.

    Let F(n):N->N be the number of integers less than or equal to n and relatively prime to it (the Euler totient function). A generalisation of FLT says that if gcd(a,n) = 1 then a^F(n) = 1 (mod n).

    Then it can be shown that:

    (a^f(n))^k = a^kF(n) = 1 (mod n)

    For integers k. So all we need is some composite n such that F(n)|(n-1). I found necessary but not sufficient conditions that can be imposed on n for the above to be true, namely that n is an odd integer that is the product of at least three distinct primes, and is not divisible by the square of any prime. The proof of this is as follows:

    To prove that it must be non-square-factorable, we realize that F is multiplicative and prove that n cannot be a square. So say n = p^2 for some prime p. Then F(n) = p^2 - p. So:

    (n-1)/F(n) = [(p+1)(p-1)]/p(p-1) = (p+1)/p which is never an integer. So n may not have a aquare factor. Now if n has only two distinct prime factors, n = pq, then:

    (m-1)/F(n) = (pq-1)/((p-1)(q-1) = 1 + 1/(q-1) + 1/(p-1) which cannot be an integer provided p and q are distinct. Thus some n satisfying your problem do exist, and are products of at least three distinct odd primes. I then fooled around with triples of small odd primes, and ruled out ones that failed to satisfy the condition F(n)|(n-1). The smallest one should be n = 3*11*17 = 561. But I am not an algebraist.
  4. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Apr '03 03:35
    And something else...7*13*19 = 1729 satisfies this! This is, of course, the number that, in his recent book, Professor Gowers calls "interesting". Could this be why?
  5. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Apr '03 14:18
    Originally posted by royalchicken
    I thought about this all afternoon, and accomplished the following:

    1.I proved that such an n exists, and that there are more than one of them, but I would not wager that they are infinite in number;

    2.I found a couple of examples of such numbers.

    Let F(n):N->N be the number of integers less than or equal to n and relatively prime to it (the Eu ...[text shortened]... ondition F(n)|(n-1). The smallest one should be n = 3*11*17 = 561. But I am not an algebraist.
    Certain parts of this are wrong or not applicable. For example, on closer inspection, F(561) = 320 which does not divide 560. And it shouldn't, for I used a similar argument to prove that for F(n)|n-1, n needs at least FOUR prime factors. So the criteria is not that F(n)|n-1. Instead, we keep FLT in mind and look at n-1-F(n). From this we can arrive at the REAL criteria:

    1.For every p|n, (p-1)|(n-1)
    2.n is not divisible by any squares
    3.n is odd and all prime factors are distinct

    So, using small primes, the first few are 561, 1105, 1729. If you'd care to continue this sequence, please do. Apologies for the partly faulty post last night.

    PS If each of the following factors is prime, it is easy to show that (6m+1)(12m+1)(18m+1) satisfies your problem. Can you prove it (1729 is the first of these.)
  6. Joined
    28 Mar '03
    Moves
    16
    05 Apr '03 23:50
    Ain't those Carmichael numbers that you are talking about?
  7. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Apr '03 23:59
    Originally posted by Mock True
    Ain't those Carmichael numbers that you are talking about?
    I don't know...if Carmichael numbers are the ones Acolyte is looking for, then yes.
  8. Donationbbarr
    Chief Justice
    Center of Contention
    Joined
    14 Jun '02
    Moves
    17381
    06 Apr '03 23:40
    Originally posted by royalchicken
    I don't know...if Carmichael numbers are the ones Acolyte is looking for, then yes.
    These are carmichael numbers:

    http://mathworld.wolfram.com/CarmichaelNumber.html
  9. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    07 Apr '03 00:42
    Originally posted by bbarr
    These are carmichael numbers:

    http://mathworld.wolfram.com/CarmichaelNumber.html
    Thanks. This was a good problem; my first criterion was a bit too strong, so I weakened it and that seems to work. Thank you for showing me wolfram.com, too...I shall have to look at it more.
Back to Top