Let be an integer of the form , where and are relatively prime integers and such that if is a prime, , then divides . Determine all such .
Answer: .
Let be an integer of the form , where and are relatively prime integers and such that if is a prime, , then divides . Determine all such .
Answer: .
A prime divides if and only if divides either or . If is a composite then it has a prime divisor , and if divides it divides and vice-versa, which is not possible because and are coprime. Therefore is a prime.
Suppose without loss of generality that and consider . Note that .
- If then because and are coprime. is a solution.
- If then and are coprime and . So any prime factor of any number smaller than is a divisor of .
One can check that and yields the solutions (the only prime is 2) and (the only primes are 2 and 3). Suppose that .
Consider, for instance, the prime factors of , which is coprime with . Any prime must then divide . Then it divides , that is, can only have 2 as a prime factor, that is, is a power of 2 , and since , is odd.
Since , we can also consider any prime divisor of . Since is odd, and are also coprime, so any prime divisor of must divide . But and are also coprime, so there can be no such primes. This is a contradiction, and does not yield any solutions.
- If , consider a prime divisor of . Since divides one of and divides both numbers (just add or subtract accordingly.) This is a contradiction.
Hence the only solutions are .