Cool modular arithmetic prob

For discussing Olympiad Level Number Theory problems
Almx26
Posts:5
Joined:Fri Aug 28, 2020 11:08 am
Location:Chattogram,Bangladesh
Contact:
Cool modular arithmetic prob

Unread post by Almx26 » Wed Jun 02, 2021 8:35 am

An infinite series of integers follows the following rule:
$a_{n+1}=2a_n +1$
Is there any $a_0$ for which every term of the series will be a prime number?

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Cool modular arithmetic prob

Unread post by Asif Hossain » Fri Jun 11, 2021 11:09 am

Almx26 wrote:
Wed Jun 02, 2021 8:35 am
An infinite series of integers follows the following rule:
$a_{n+1}=2a_n +1$
Is there any $a_0$ for which every term of the series will be a prime number?
Is there any recipe to cook prime numbers? :o
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Cool modular arithmetic prob

Unread post by Mehrab4226 » Sun Jun 13, 2021 6:59 am

Almx26 wrote:
Wed Jun 02, 2021 8:35 am
An infinite series of integers follows the following rule:
$a_{n+1}=2a_n +1$
Is there any $a_0$ for which every term of the series will be a prime number?
Clearly, the first term of the sequence $a_0$ must be a prime,
Now look at the sequence,
$a_{n+1}=2a_n+1$
This can be rephrased as
$a_{n+1}=2^{n+1}a_0+2^{n+1}-1$
Because if we think the sequence in binary we will see that what the sequence is doing is adding a digit $1$ in the end which is the same as multiplying a number by a power of $2$ which will then create a number of $0$ digits in the end of the number equal to the power of $2$ which is then added with the same number of $1$ s. An example will make things clear.
If $a_0=5=(101)_2$
$\to a_1=11=(1011)_2$[$1011$ is the same as $1010 +1$ which is just doubling $5$ and adding $2-1$ with it]
$\to a_2=23=(10111)_2$[$10111$ is the same as $10100+11$ which is $2^2 \times 5 +2^2-1$]
Now by fermat's little theorem we get,
$2^{p-1}-1 \equiv 0(\text{mod p})$
so $2^{p-1}-1=kp$
So if $a_0=p$
then $a_{p-1}=2^{p-1}p+2^{p-1}-1=2^{p-1}p+kp$ which is composite.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Cool modular arithmetic prob

Unread post by Mehrab4226 » Sun Jun 13, 2021 8:29 pm

Mehrab4226 wrote:
Sun Jun 13, 2021 6:59 am
Almx26 wrote:
Wed Jun 02, 2021 8:35 am
An infinite series of integers follows the following rule:
$a_{n+1}=2a_n +1$
Is there any $a_0$ for which every term of the series will be a prime number?
Clearly, the first term of the sequence $a_0$ must be a prime,
Now look at the sequence,
$a_{n+1}=2a_n+1$
This can be rephrased as
$a_{n+1}=2^{n+1}a_0+2^{n+1}-1$
Because if we think the sequence in binary we will see that what the sequence is doing is adding a digit $1$ in the end which is the same as multiplying a number by a power of $2$ which will then create a number of $0$ digits in the end of the number equal to the power of $2$ which is then added with the same number of $1$ s. An example will make things clear.
If $a_0=5=(101)_2$
$\to a_1=11=(1011)_2$[$1011$ is the same as $1010 +1$ which is just doubling $5$ and adding $2-1$ with it]
$\to a_2=23=(10111)_2$[$10111$ is the same as $10100+11$ which is $2^2 \times 5 +2^2-1$]
Now by fermat's little theorem we get,
$2^{p-1}-1 \equiv 0(\text{mod p})$
so $2^{p-1}-1=kp$
So if $a_0=p$
then $a_{p-1}=2^{p-1}p+2^{p-1}-1=2^{p-1}p+kp$ which is composite.
There is actually a silly hole(mistake) in the solution. You guys can find it out. Not something that will get 0.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply