Browse Groups

• Hi: According to The Prime Glossary, a composite is a Carmichael number a^(n-1)==1 (mod n) for every a relatively prime to n. I ask: There s no bound to a in
Message 1 of 3 , Jul 1, 2004
View Source
Hi:

According to The Prime Glossary, a composite is a Carmichael number a^(n-1)==1 (mod n) for every a relatively prime to n.

I ask: There's no bound to a in the definition? Something like a<=n-1. If it actually is for every a, then I can't see how you prove a precise number (like 561) being a Carmichael.

But if a is bounded, then I see no problem with Carmichaels in primality testing... just take the a's over the bound.

Jose Brox
http://espanol.groups.yahoo.com/group/Telecomunicacion/
(www.brox.tk)
ambroxius@...

[Non-text portions of this message have been removed]
• ... Hash: SHA1 ... But by the Fermat-Euler Theorem: a^phi(n) == 1 (mod n) for any a != 0. Thus any a s lying in the same residue class modulo phi(n) are
Message 1 of 3 , Jul 1, 2004
View Source
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 01 July 2004 20:19, you wrote:
> Hi:
>
> According to The Prime Glossary, a composite is a Carmichael number
> a^(n-1)==1 (mod n) for every a relatively prime to n.
>
> I ask: There's no bound to a in the definition? Something like a<=n-1. If
> it actually is for every a, then I can't see how you prove a precise number
> (like 561) being a Carmichael.

But by the Fermat-Euler Theorem:

a^phi(n) == 1 (mod n)

for any a != 0. Thus any a's lying in the same residue class modulo phi(n) are
equivalent.

> But if a is bounded, then I see no problem with Carmichaels in primality
> testing... just take the a's over the bound.

Since they `wrap around' phi(n), you can't do that.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFA5KUUMvCZlCdExvkRAgZKAJ9AwoGUVYPWWD6e0FyFZ0hAHJX7HgCfdr22
YPY5+kV3PPOoehAI9kwRN18=
=g/gx
-----END PGP SIGNATURE-----
• ... (mod n) for every a relatively prime to n. Yes, the definition says the composite n is a Carmichael number iff: a^(n-1)==1 (mod n) for every a relatively
Message 1 of 3 , Jul 1, 2004
View Source
Jose Ramón Brox wrote:
> According to The Prime Glossary, a composite is a Carmichael number a^(n-1)==1
(mod n) for every a relatively prime to n.

Yes, the definition says the composite n is a Carmichael number iff:
a^(n-1)==1 (mod n) for every a relatively prime to n

> I ask: There's no bound to a in the definition? Something like a<=n-1. If it
actually is for every a, then I can't see how you prove a precise number (like
561) being a Carmichael.

There are definitions, and then there is a nice little thing mathematicians are
rather fond of: Theorems.
It is trivial to show that a<=n-1 is sufficient. It follows immediately from the
simple rule:
If a==b (mod n) then a^x == b^x (mod n).

Example of more complicated theorem: x is a Carmichael number (i.e. satisfies
the definition) if the prime factorization is on the form
(6n+1)*(12n+1)*(18n+1). The proof is omitted.
(There are many other Carmichael numbers).

> But if a is bounded, then I see no problem with Carmichaels in primality
testing... just take the a's over the bound.

A finite bound can still be infeasible, and it is for large prp's.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.