Power Full Integers
We will call a positive integer N powerful if a 2 N ≡ 1 ( m o d N ) for all integers a that are coprime to N . How many odd three-digit numbers are powerful?
Note: You may find it useful to refer to this List of Primes .
The answer is 9.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
There is a non-exhaustive search to this problem, which requires you to understand the underlying structure of the problem. As a hint, the start of the solution is:
Suppose p is any (odd) prime factor of N . Because the multiplicative group modulo p is cyclic, there exists some integer g , coprime to p , such that g k ≡ 1 ( m o d p ) if and only if k is a multiple of p − 1 (aka primitive element theorem). Therefore, for any powerful N and for any of its prime factors p , we have p − 1 ∣ 2 N , which is a necessary and sufficient condition.
You then continue from here, making observations as to what prime factors are valid. For example, you can show that p ≡ 3 ( m o d 4 ) , and p = 1 1 .
@Daniel Liu Here's a problem that uses the primitive element theorem.
No simpler way?
Exaustive search gives that there are only 10 odd numbers N ∈ [ 1 0 0 , 9 9 9 ] such that 4 N ≡ 1 ( m o d N ) ; they are all multiples of 3: 1 4 7 , 1 7 1 , 1 8 9 , 2 4 3 , 4 4 1 , 5 1 3 , 5 6 7 , 6 5 7 , 7 2 9 , 9 0 3 . By testing them one by one I found that only 657 fails to be a "half-Carmicheal" number.