How to check if a property applies to all coprimes of a number?

Posted on 2008-11-22 08:51 By pyr0rrzzz (6)

Categories:

How do I ...? with Maple (Student)

Hi, I'm rather new to Maple but I have to find a composite number n which has the property that all her coprimes a fulfill the expression "a^(n-1) - 1 mod n = 0". I already found out that such numbers are called Carmichael numbers. But of course I need to use Maple and the information I was given by our professor.
My problem is that I have no idea how to check if "a^(n-1) - 1 mod n = 0" is true for all coprimes of a given n. How do I? ;)

btw. I don't know if I used the correct vocabulary here, so please forgive me if I expressed something wrong.

code

Comment on 2008-11-22 10:54 from acer ( Maple Rating 4

1410)

Using a translation of the Mma code here to get Carmichael numbers,

> seq(`if`(modp(n,numtheory[lambda](n))=1 and
>          not isprime(n), n, NULL), n=1..10000);
                    561, 1105, 1729, 2465, 2821, 6601, 8911

See the Comment section at that link.

acer

Thank you, now I just need

Comment on 2008-11-22 11:04 from pyr0rrzzz (6)

Thank you, now I just need to understand how I could've found this myself.

... and ...

Comment on 2008-11-22 19:41 from edgar ( Maple Rating 2

186)

And probably the professor wanted *him* to program it, rather than using some pre-programmed "lambda" function.
---
G A Edgar

Hint

Comment on 2008-11-23 03:04 from Robert Israel ( Maple Rating 4

1555)

The straightforward way (without using lambda), given n, is to start with the
set of integers {$1..n-1}, select those coprime to n (using select and igcd),
and compute a^(n-1) mod n for all those a.

^ That sounds good. I'm

Comment on 2008-11-23 10:06 from pyr0rrzzz (6)

^ That sounds good, I'm going to try it. But why do I only need to check the property for all the coprimes smaller than n? I mean, there is most likely an infinite number of coprimes greater than n, too.

EDIT: I came up with the following code. I bet it's a mess: