Powers of 102?
Let A = 1 0 2 1 , 1 0 2 2 , 1 0 2 3 , ⋯ . How many primes p are there such that A has at least one element a such that a ≡ − 1 (mod p) ?
For example, one such prime is 1 0 3 , because 1 0 2 1 ≡ − 1 (mod 103) .
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.
3 solutions
I don't quite understand: how does proving they are coprime mean there are infinitely many primes dividing 1 0 2 t + 1 ? And what's t?
Log in to reply
Take $t$ to be powers of $2$.
102^{2^1}+1, 102^{2^2}+1, 102^{2^3}+1, ..., 102^{2^k}+1 are all relative prime to each other. Now for each number in this series, either the number itself is prime, or the number is a product of primes, but in any case, these prime(s) cannot be shared amongst other numbers in the series. So every number in the series adds at least one new prime to a list of primes.
My rationale was simply that A is a set with an infinite number of elements. And there are an infinite number of prime numbers. Therefore, there must be an infinite number of primes p . Correct me if I am wrong.
Log in to reply
Consider the set { 2 , 4 , 6 , 8 , 1 0 , . . . } - there are an infinite number of integers in this set too - therefore by your logic, an infinite number of these must be prime.
You can also just suppose there are only finitely many primes that do this, p 1,...p k. Notice they cant divide 102. Then look at 102 to the power of the product of these primes minus 1, i.e. 102^(p 1-1)(p 2-1)... (p k-1). This will be congruent to 1 mod p i for all such p i, by fermat's little theorem. So adding one will not be congruent to -1 modp i for all i, since non of the p_i =2. But clearly this number is divisible by some prime, not in our list.
Log in to reply
Oops, I mixed up what I was trying to do. What I originally used was that the multiplicative subgroup without 0 of Z_p is cyclic, but that is not elementary so I tried to do something different and got mixed up. Oh well.
Log in to reply
Sorry, let me clarify, my solution does work, but when I originally did it, I was able to sort of say precisely what form the non valid primes would be, but I cant do that this way.
Oops there are mistakes in my sketch below, but the strategy does work. Im sure there is enough info to figure out the correct thing I should have said at the end. :-)
How does ( 1 0 2 2 k ) 2 k − l ≡ 1 ( m o d p ) ⟹ 1 0 2 2 l ≡ 1 ?
There might be a mistake. I'd say it should be changed to "Assume WLOG that k < l ", and in the second step, we get
⇒ ( 1 0 2 2 k ) 2 l − k = …
Otherwise, it seems to be correct. And before I forget: This is beautiful!
This is a very well thought-out proof, and much more elegant than mine.
We can rewrite a ≡ − 1 (mod p) as a + 1 ≡ 0 (mod p) . Now, we look back to our original sequence. We note that the only primes which will divide terms in this sequence are 2 , 3 , 1 7 . Thus, we apply Kobayachi's Theorem, which states that if an infinite sequence of positive integers S only has a finite number of prime divisors (a prime divisor of a sequence is a prime that divides a term of the sequence), then shifting all of the terms by any positive integer will yield a new set, S ′ , which has an infinite number of prime divisors. We let the sequence S be A , the positive integer by which we shift be 1 , and it follows that there are an infinite number of primes which satisfy this property.
It seems to me that there should be a proof by contradiction using Euler's Theorem, but for now it eludes me.
Well, I think a majority of Brilliantians won't have any knowledge of any Kobayachi's Theorem! Can you please illustrate a simple understandable proof of Kobayachi's theorem for all of us?
Log in to reply
I can't think of a simple proof of the entire statement of Kobayashi's Theorem off of the top of my head, although I think that I can make a convincing argument for powers of some integer x where t = 1 , which is all we really need for this problem.
We proceed by contradiction. We let p be a prime that doesn't divide x . We look at the value x p − 1 , which, by Euler's Theorem, is equivalent to 1 mod p , so we have proved Kobayashi's theorem for t = − 1 . Now, look at the sequence B 1 = 2 , x + 1 , x 2 + 1 , ⋯ , and the sequence B − 1 = 0 , x − 1 , x 2 − 1 , ⋯ . Now, let n be a prime divisor of B − 1 . Note that n divides x n − 1 − 1 . Now, if there exists an integer k such that x k ≡ − 1 mod n , then x n − 1 + k + 1 is also divisible by n . Since x and n are relatively prime, powers of x take on every possible residue mod n (I think, although I don't know if I can prove this), so n divides some term of B 1 as well, so the number of prime divisors of B 1 is infinite.
Log in to reply
Wait no my last statement is false. I do think, whoever, that powers of x take on the value of − 1 (mod n) , although again, I can't prove it.
My rationale was simply that A is a set with an infinite number of elements. And there are an infinite number of prime numbers. Therefore, there must be an infinite number of primes p . Correct me if I am wrong.
Do you mean using euclid's theorem? I believe I gave a sketch of it in a comment to Rahul Saha's solution.
One of the solution is to use the Zsigsmondy Theorem, which states that there exists a primitive prime divisor of $a^n+1$, exept for $a=6$ and $n=3$
We show that g cd ( 1 0 2 2 k + 1 , 1 0 2 2 l + 1 ) = 1 by emulating the proof that any two different Fermat numbers are coprime. Suppose that there exists a prime p that divides both 1 0 2 2 k + 1 and 1 0 2 2 l + 1 , where k = l . Assume WOLOG that k > l . Then, 1 0 2 2 k ≡ − 1 ( m o d p ) ⟹ ( 1 0 2 2 k ) 2 k − l ≡ ( − 1 ) 2 l − k ≡ 1 ( m o d p ) ⟹ 1 0 2 2 l ≡ 1 ( m o d p )
Now this means that p divides both 1 0 2 2 l + 1 and 1 0 2 2 l − 1 which implies p divides 2 , clearly a contradiction.
Now this implies that there exists infinitely many primes that divide 1 0 2 t + 1 for t = 1 , 2 , ⋯ .