Power to Ramanujan in 2017
x 1 7 2 9 ≡ 1 ( m o d 2 0 1 7 )
How many positive integer solutions x < 2 0 1 7 does the congruency above have?
The answer is 7.
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
Yes, well explained! (+1) Some people might need a little further explanation as to why x 1 7 2 9 ≡ 1 implies x 7 ≡ 1 ( m o d 2 0 1 7 ) .
Log in to reply
Does it have to do with the property of modular exponentiation?
Log in to reply
I thought about it this way when I wrote the problem: Let g be a multiplicative generator and write x = g m for 1 ≤ m ≤ 2 0 1 6 , so that our equation becomes g 1 7 2 9 m ≡ 1 ( m o d 2 0 1 7 ) . It is required that 2 0 1 6 ∣ 1 7 2 9 m or 2 8 8 ∣ 2 4 7 m or 2 8 8 ∣ m . There are 7 such values for m , namely, m = 2 8 8 k for k = 1 , . . , 7 .
Does this make sense?
Log in to reply
@Otto Bretscher – I arrived to x 7 ≡ 1 ( m o d 2 0 1 7 ) because we know that x 1 7 2 9 ≡ 1 ( m o d 2 0 1 7 ) and so for Fermat's theorem x 1 7 2 9 × x 2 8 7 ≡ x 2 0 1 6 ≡ 1 ( m o d 2 0 1 7 ) and x 2 8 7 ≡ 1 ( m o d 2 0 1 7 ) . Then x 2 8 7 6 ≡ x 1 7 2 2 ≡ 1 ( m o d 2 0 1 7 ) . And so x 1 7 2 2 × x 7 ≡ x 1 7 2 9 ≡ 1 ( m o d 2 0 1 7 ) . The result is x 7 ≡ 1 ( m o d 2 0 1 7 ) .
Log in to reply
@Alex Spagnoletti – Yes, indeed, x 7 ≡ 1 ( m o d 2 0 1 7 ) is equivalent to x 1 7 2 9 ≡ 1 . The quickest way to see this is to exponentiate by 247 to go one way and by 7 to go back.
Since 7 divides 1 7 2 9 , it is clear that x 7 ≡ 1 implies x 1 7 2 9 ≡ 1 .
Since the HCF of 1 7 2 9 and 2 0 1 6 is 7 , we can find integers a , b such that 1 7 2 9 a + 2 0 1 6 b = 7 . Since Z 2 0 1 7 × has order 2 0 1 6 , we have that x 2 0 1 6 ≡ 1 for all elements of the group. Thus x 1 7 2 9 ≡ 1 implies x 7 ≡ 1 .
Thus the equations x 1 7 2 9 ≡ 1 and x 7 ≡ 1 are equivalent, modulo 2 0 1 7 .
Since 2 0 1 7 is prime, the set Z 2 0 1 7 × of nonzero residues modulo 2 0 1 7 is a group under multiplication modulo 2 0 1 7 ; indeed, it is a cyclic group of order 2 0 1 6 , being the group of nonzero elements of a finite field.
The highest common factor of 1 7 2 9 and 2 0 1 6 is 7 , and hence x 1 7 2 9 ≡ 1 in Z 2 0 1 7 × precisely when x 7 ≡ 1 in Z 2 0 1 7 × . In other words, we want to know how many 7 th roots of unity there are in Z 2 0 1 7 × .
Since Z 2 0 1 7 × is a cyclic group of order 2 0 1 6 , it has a generator u of order 2 0 1 6 . An element x in Z 2 0 1 7 × satisfies the equation x 7 ≡ 1 in Z 2 0 1 7 × precisely when x = u k for some integer k , where u 7 k ≡ 1 , and hence 2 0 1 6 divides 7 k . Thus we deduce that 2 8 8 must divide k . The seventh roots of unity in Z 2 0 1 7 × are the powers u 2 8 8 j for j = 0 , 1 , 2 , 3 , 4 , 5 , 6 ; there are 7 of them.