Find the value of the 80th smallest positive integer that is coprime to 9955.
Note: If is coprime to , then and don't share any common factor other than 1.
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.
First we note the prime factorization 9 9 5 5 = 5 × 1 1 × 1 8 1 .
So every positive integer that is not a positive multiple of any of 5 , 1 1 or 1 8 1 will be coprime to 9 9 5 5 . Assuming for the moment that the 8 0 th such coprime integer is less than 1 8 1 , we are looking for the least positive integer N such that
N − ( ⌊ 5 N ⌋ + ⌊ 1 1 N ⌋ − ⌊ 5 5 N ⌋ ) = 8 0 .
As a means of expediting a solution, suppose for the moment that N is divisible by 5 5 . Then this equation becomes
N − ( 5 N + 1 1 N − 5 5 N ) = 8 0 ⟹ 5 5 4 0 N = 8 0 ⟹ N = 1 1 0 .
So there are 8 0 integers less than or equal to 1 1 0 that are coprime to 9 9 5 5 . But since 1 1 0 itself is not coprime to 9 9 5 5 , we can conclude that 1 0 9 is in fact the 8 0 th smallest positive integer that is coprime to 9 9 5 5 .