Mixing
Proving $10240…02401$ composite
Clash Royale CLAN TAG#URR8PPP
up vote
19
down vote
favorite
I got this question recently, and have been unable to solve it.
Prove that $1024underbrace00 ldotsldots 00_2014 text times2401$ is composite.
I have two different ways in mind.
First is $7^4+400(2^2cdot10^504)^4$, which looks like Sophie Germain, but I'm not sure what to do with the $400$. Another thought is that this is almost a palindrome, with the order of just two digits interchanged. I'm not sure where to go from there, and if it'd provide any results, but it seems interesting nonetheless.
Please help.
elementary-number-theory contest-math arithmetic
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
 |Â
show 15 more comments
up vote
19
down vote
favorite
I got this question recently, and have been unable to solve it.
Prove that $1024underbrace00 ldotsldots 00_2014 text times2401$ is composite.
I have two different ways in mind.
First is $7^4+400(2^2cdot10^504)^4$, which looks like Sophie Germain, but I'm not sure what to do with the $400$. Another thought is that this is almost a palindrome, with the order of just two digits interchanged. I'm not sure where to go from there, and if it'd provide any results, but it seems interesting nonetheless.
Please help.
elementary-number-theory contest-math arithmetic
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
3
What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$.
– Surb
Jul 27 at 9:23
1
It means that $1024$ and $2401$ have $2014text '0's$ between them.
– MalayTheDynamo
Jul 27 at 9:24
2
Am I right in thinking that your number has $2022$ digits of which $2016$ are zero?
– Mark Bennet
Jul 27 at 9:28
2
@Servaes The strong Fermat test to base $2$ says it's composite.
– Daniel Fischer♦
Jul 27 at 11:24
4
@Servaes Write $n-1 = 2^kcdot m$ with $m$ odd, and then $$a^n-1 - 1 = (a^m - 1)prod_kappa = 0^k-1bigl(a^2^kappa m + 1bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m equiv 1 pmodn$ or there is a $kappa in 0,dotsc, k-1$ such that $a^2^kappam equiv -1pmodn$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.)
– Daniel Fischer♦
Jul 27 at 11:50
 |Â
show 15 more comments
up vote
19
down vote
favorite
up vote
19
down vote
favorite
I got this question recently, and have been unable to solve it.
Prove that $1024underbrace00 ldotsldots 00_2014 text times2401$ is composite.
I have two different ways in mind.
First is $7^4+400(2^2cdot10^504)^4$, which looks like Sophie Germain, but I'm not sure what to do with the $400$. Another thought is that this is almost a palindrome, with the order of just two digits interchanged. I'm not sure where to go from there, and if it'd provide any results, but it seems interesting nonetheless.
Please help.
elementary-number-theory contest-math arithmetic
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
I got this question recently, and have been unable to solve it.
Prove that $1024underbrace00 ldotsldots 00_2014 text times2401$ is composite.
I have two different ways in mind.
First is $7^4+400(2^2cdot10^504)^4$, which looks like Sophie Germain, but I'm not sure what to do with the $400$. Another thought is that this is almost a palindrome, with the order of just two digits interchanged. I'm not sure where to go from there, and if it'd provide any results, but it seems interesting nonetheless.
Please help.
elementary-number-theory contest-math arithmetic
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
edited Jul 27 at 9:35
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
asked Jul 27 at 9:14
MalayTheDynamo
2,052833
2,052833
3
What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$.
– Surb
Jul 27 at 9:23
1
It means that $1024$ and $2401$ have $2014text '0's$ between them.
– MalayTheDynamo
Jul 27 at 9:24
2
Am I right in thinking that your number has $2022$ digits of which $2016$ are zero?
– Mark Bennet
Jul 27 at 9:28
2
@Servaes The strong Fermat test to base $2$ says it's composite.
– Daniel Fischer♦
Jul 27 at 11:24
4
@Servaes Write $n-1 = 2^kcdot m$ with $m$ odd, and then $$a^n-1 - 1 = (a^m - 1)prod_kappa = 0^k-1bigl(a^2^kappa m + 1bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m equiv 1 pmodn$ or there is a $kappa in 0,dotsc, k-1$ such that $a^2^kappam equiv -1pmodn$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.)
– Daniel Fischer♦
Jul 27 at 11:50
 |Â
show 15 more comments
3
What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$.
– Surb
Jul 27 at 9:23
1
It means that $1024$ and $2401$ have $2014text '0's$ between them.
– MalayTheDynamo
Jul 27 at 9:24
2
Am I right in thinking that your number has $2022$ digits of which $2016$ are zero?
– Mark Bennet
Jul 27 at 9:28
2
@Servaes The strong Fermat test to base $2$ says it's composite.
– Daniel Fischer♦
Jul 27 at 11:24
4
@Servaes Write $n-1 = 2^kcdot m$ with $m$ odd, and then $$a^n-1 - 1 = (a^m - 1)prod_kappa = 0^k-1bigl(a^2^kappa m + 1bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m equiv 1 pmodn$ or there is a $kappa in 0,dotsc, k-1$ such that $a^2^kappam equiv -1pmodn$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.)
– Daniel Fischer♦
Jul 27 at 11:50
3
3
What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$.
– Surb
Jul 27 at 9:23
What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$.
– Surb
Jul 27 at 9:23
1
1
It means that $1024$ and $2401$ have $2014text '0's$ between them.
– MalayTheDynamo
Jul 27 at 9:24
It means that $1024$ and $2401$ have $2014text '0's$ between them.
– MalayTheDynamo
Jul 27 at 9:24
2
2
Am I right in thinking that your number has $2022$ digits of which $2016$ are zero?
– Mark Bennet
Jul 27 at 9:28
Am I right in thinking that your number has $2022$ digits of which $2016$ are zero?
– Mark Bennet
Jul 27 at 9:28
2
2
@Servaes The strong Fermat test to base $2$ says it's composite.
– Daniel Fischer♦
Jul 27 at 11:24
@Servaes The strong Fermat test to base $2$ says it's composite.
– Daniel Fischer♦
Jul 27 at 11:24
4
4
@Servaes Write $n-1 = 2^kcdot m$ with $m$ odd, and then $$a^n-1 - 1 = (a^m - 1)prod_kappa = 0^k-1bigl(a^2^kappa m + 1bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m equiv 1 pmodn$ or there is a $kappa in 0,dotsc, k-1$ such that $a^2^kappam equiv -1pmodn$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.)
– Daniel Fischer♦
Jul 27 at 11:50
@Servaes Write $n-1 = 2^kcdot m$ with $m$ odd, and then $$a^n-1 - 1 = (a^m - 1)prod_kappa = 0^k-1bigl(a^2^kappa m + 1bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m equiv 1 pmodn$ or there is a $kappa in 0,dotsc, k-1$ such that $a^2^kappam equiv -1pmodn$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.)
– Daniel Fischer♦
Jul 27 at 11:50
 |Â
show 15 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864212%2fproving-10240-02401-composite%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
3
What does "102400...(2014 times)...002401" mean? It's not clear to me what should be the $...$.
– Surb
Jul 27 at 9:23
1
It means that $1024$ and $2401$ have $2014text '0's$ between them.
– MalayTheDynamo
Jul 27 at 9:24
2
Am I right in thinking that your number has $2022$ digits of which $2016$ are zero?
– Mark Bennet
Jul 27 at 9:28
2
@Servaes The strong Fermat test to base $2$ says it's composite.
– Daniel Fischer♦
Jul 27 at 11:24
4
@Servaes Write $n-1 = 2^kcdot m$ with $m$ odd, and then $$a^n-1 - 1 = (a^m - 1)prod_kappa = 0^k-1bigl(a^2^kappa m + 1bigr)$$ where $1 < a < n-1$. Then $n$ is a strong Fermat probable prime if $n$ divides one of the factors of the product, i.e. $a^m equiv 1 pmodn$ or there is a $kappa in 0,dotsc, k-1$ such that $a^2^kappam equiv -1pmodn$. That's the test Miller-Rabin is composed of. In this case, $a = 2$ shows it's composite. (Actually already the ordinary Fermat test shows that here.)
– Daniel Fischer♦
Jul 27 at 11:50