The Converse of Little Theorem

Carmichael numbers

Java solution: import java.math.BigInteger; import java.util.ArrayList; public class Main {

     public static void main(String []args) {
        ArrayList<Integer> primes = new ArrayList<>();
        primes.add(2);
        primeloop:
        for (int i = 3; i < 1000; i++) {
            for (int prime : primes) {
                if (i % prime == 0) {
                    continue primeloop;
                }
            }
            primes.add(i);
        }
        loop:
        for (int n = 1; n < 1000; n++) {
            if (primes.contains(n)) {
                continue loop;
            }
            for (int a = 1; a < 100; a++) {
                BigInteger num = new BigInteger(a + "");
                BigInteger other = num.pow(n);
                other = other.subtract(new BigInteger(a + ""));
                if (other.mod(new BigInteger(n + "")).intValue() != 0) {
                    continue loop;
                }
            }
            System.out.println(n);
        }
     }
}

Explanation: This finds all primes between 1 and 1000 and adds them to a list, then goes through and tests each that is not a prime to see if all it satisfies the rule for all integer values of a from 1-100. I had to use BigInteger because a normal int or long can't handle the insanely large values that you get when doing operations which go as high as 1000^100.

The answer is $\fbox{561}$ . This is the subject of the wiki on Carmichael numbers , which is currently inactive (someone should fill it in!). The result is mentioned in the wiki on Carmichael's lambda function .