Primes of the form $ varphi(n)^varphi(n)+n $ or $ n^n+varphi(n) $ for composite $n$?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
This question :
Do further prime numbers of the form $n^n+varphi(n)$ exist?
deals about prime numbers of the form $$n^n+varphi(n)$$
I know no composite number $n$, such that this expression is prime.
Strangely, I neither know a composite $n$ such that $$varphi(n)^varphi(n)+n$$ is prime. This expression is prime for $n=1,2,3,7,463$ and no other $nle 1 000$.
Is it a coincidence that I did not find a composite number $n$ such that either expression is a prime, or can it be proven that we never get a prime for composite $n$ ?
number-theory elementary-number-theory prime-numbers totient-function
asked Aug 11 at 23:18
Peter
45.3k939119
add a comment |Â
up vote
2
down vote
favorite
This question :
Do further prime numbers of the form $n^n+varphi(n)$ exist?
deals about prime numbers of the form $$n^n+varphi(n)$$
I know no composite number $n$, such that this expression is prime.
Strangely, I neither know a composite $n$ such that $$varphi(n)^varphi(n)+n$$ is prime. This expression is prime for $n=1,2,3,7,463$ and no other $nle 1 000$.
Is it a coincidence that I did not find a composite number $n$ such that either expression is a prime, or can it be proven that we never get a prime for composite $n$ ?
number-theory elementary-number-theory prime-numbers totient-function
asked Aug 11 at 23:18
Peter
45.3k939119
As usual, questions about primes of a given form receive at least one downvote :)
– Peter
Aug 12 at 12:03
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
This question :
Do further prime numbers of the form $n^n+varphi(n)$ exist?
deals about prime numbers of the form $$n^n+varphi(n)$$
I know no composite number $n$, such that this expression is prime.
Strangely, I neither know a composite $n$ such that $$varphi(n)^varphi(n)+n$$ is prime. This expression is prime for $n=1,2,3,7,463$ and no other $nle 1 000$.
Is it a coincidence that I did not find a composite number $n$ such that either expression is a prime, or can it be proven that we never get a prime for composite $n$ ?
number-theory elementary-number-theory prime-numbers totient-function
asked Aug 11 at 23:18
Peter
45.3k939119
This question :
Do further prime numbers of the form $n^n+varphi(n)$ exist?
deals about prime numbers of the form $$n^n+varphi(n)$$
I know no composite number $n$, such that this expression is prime.
Strangely, I neither know a composite $n$ such that $$varphi(n)^varphi(n)+n$$ is prime. This expression is prime for $n=1,2,3,7,463$ and no other $nle 1 000$.
Is it a coincidence that I did not find a composite number $n$ such that either expression is a prime, or can it be proven that we never get a prime for composite $n$ ?
number-theory elementary-number-theory prime-numbers totient-function
asked Aug 11 at 23:18
Peter
45.3k939119
edited Aug 11 at 23:21
asked Aug 11 at 23:18
Peter
45.3k939119
asked Aug 11 at 23:18
Peter
45.3k939119
asked Aug 11 at 23:18
Peter
45.3k939119
45.3k939119
As usual, questions about primes of a given form receive at least one downvote :)
– Peter
Aug 12 at 12:03
add a comment |Â
As usual, questions about primes of a given form receive at least one downvote :)
– Peter
Aug 12 at 12:03
As usual, questions about primes of a given form receive at least one downvote :)
– Peter
Aug 12 at 12:03
As usual, questions about primes of a given form receive at least one downvote :)
– Peter
Aug 12 at 12:03
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
Partial answer.
Theorem: Any group of order $n$ is cyclic $Longleftrightarrow gcd(n,varphi(n))=1$
It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+varphi(n)$ and $varphi(n)^varphi(n)+n$ is a prime.
This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3times 5$ with $3notmid (5-1)$).
See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $varphi(n)^varphi(n)equiv 1bmod n$.
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
1
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
add a comment |Â
up vote
2
down vote
The expression $$varphi(n)^varphi(n)+n$$ is probable prime for $n=3113$ and $3157$ which are both composite. But for $n^n+varphi(n)$ I still do not know an example.
Smallest current candidate : $n=14 199$ ($58 958$ digits)
Candidates (no prime factor below $10^8$) :
[14199, 14227, 14231, 14237, 14253, 14295, 14363, 14381, 14479, 14485, 14501, 14
521, 14567, 14587, 14655, 14665, 14731, 14803, 14829, 14947, 14971, 14983, 15089
, 15091, 15133, 15179, 15191, 15199, 15203, 15281, 15307, 15331, 15391, 15411, 1
5415, 15481, 15505, 15509, 15535, 15573, 15701, 15739, 15821, 15917, 15919, 1596
7, 15999, 16003, 16021, 16059, 16063, 16157, 16213, 16291, 16295, 16483, 16511,
16541, 16543, 16545, 16565, 16583, 16603, 16615, 16617, 16635, 16711, 16717, 167
39, 16747, 16757, 16759, 16795, 16801, 16853, 16859, 16903, 16915, 16945, 16973,
17009, 17079, 17083, 17089, 17107, 17113, 17167, 17177, 17191, 17209, 17243, 17
377, 17383, 17411, 17413, 17437, 17467, 17491, 17495, 17741, 17815, 17851, 17953
, 17969, 17971, 17993, 18001, 18011, 18053, 18079, 18157, 18221, 18223, 18345, 1
8381, 18545, 18551, 18565, 18607, 18641, 18653, 18689, 18737, 18799, 18877, 1892
9, 18979, 18985, 19049, 19059, 19077, 19087, 19127, 19189, 19207, 19229, 19231,
19247, 19327, 19331, 19347, 19349, 19357, 19397, 19423, 19441, 19487, 19501, 195
37, 19653, 19699, 19759, 19769, 19843, 19967]
answered Aug 11 at 23:51
Peter
45.3k939119
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Partial answer.
Theorem: Any group of order $n$ is cyclic $Longleftrightarrow gcd(n,varphi(n))=1$
It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+varphi(n)$ and $varphi(n)^varphi(n)+n$ is a prime.
This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3times 5$ with $3notmid (5-1)$).
See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $varphi(n)^varphi(n)equiv 1bmod n$.
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
1
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
add a comment |Â
up vote
3
down vote
Partial answer.
Theorem: Any group of order $n$ is cyclic $Longleftrightarrow gcd(n,varphi(n))=1$
It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+varphi(n)$ and $varphi(n)^varphi(n)+n$ is a prime.
This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3times 5$ with $3notmid (5-1)$).
See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $varphi(n)^varphi(n)equiv 1bmod n$.
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
1
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Partial answer.
Theorem: Any group of order $n$ is cyclic $Longleftrightarrow gcd(n,varphi(n))=1$
It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+varphi(n)$ and $varphi(n)^varphi(n)+n$ is a prime.
This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3times 5$ with $3notmid (5-1)$).
See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $varphi(n)^varphi(n)equiv 1bmod n$.
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
Partial answer.
Theorem: Any group of order $n$ is cyclic $Longleftrightarrow gcd(n,varphi(n))=1$
It follows that if there is a non-cyclic group of order $n$, then neither of $n^n+varphi(n)$ and $varphi(n)^varphi(n)+n$ is a prime.
This means that $n$ needs to be a product of distinct primes none of which divides another lowered by $1$ (e.g. $15=3times 5$ with $3notmid (5-1)$).
See OEIS A003277. Funny fact, although I don't see how that can really be relevant here, that for such numbers, $varphi(n)^varphi(n)equiv 1bmod n$.
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
edited Aug 11 at 23:39
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
answered Aug 11 at 23:25
Arnaud Mortier
19.3k22159
19.3k22159
1
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
add a comment |Â
1
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
1
1
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
I wonder whether $$133^133+108$$ for example, has algebraic or aurifeuillan factors. According to my ECM-calculation, the smallest prime factor of this composite $283$-digit number has probably more than $30$ digits.
– Peter
Aug 11 at 23:32
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
(+1) especially because of the congruence $$varphi(n)^varphi(n)equiv 1mod n$$ which is a consequence of Euler's theorem and $gcd(n,varphi(n))=1$
– Peter
Aug 11 at 23:46
add a comment |Â
up vote
2
down vote
The expression $$varphi(n)^varphi(n)+n$$ is probable prime for $n=3113$ and $3157$ which are both composite. But for $n^n+varphi(n)$ I still do not know an example.
Smallest current candidate : $n=14 199$ ($58 958$ digits)
Candidates (no prime factor below $10^8$) :
[14199, 14227, 14231, 14237, 14253, 14295, 14363, 14381, 14479, 14485, 14501, 14
521, 14567, 14587, 14655, 14665, 14731, 14803, 14829, 14947, 14971, 14983, 15089
, 15091, 15133, 15179, 15191, 15199, 15203, 15281, 15307, 15331, 15391, 15411, 1
5415, 15481, 15505, 15509, 15535, 15573, 15701, 15739, 15821, 15917, 15919, 1596
7, 15999, 16003, 16021, 16059, 16063, 16157, 16213, 16291, 16295, 16483, 16511,
16541, 16543, 16545, 16565, 16583, 16603, 16615, 16617, 16635, 16711, 16717, 167
39, 16747, 16757, 16759, 16795, 16801, 16853, 16859, 16903, 16915, 16945, 16973,
17009, 17079, 17083, 17089, 17107, 17113, 17167, 17177, 17191, 17209, 17243, 17
377, 17383, 17411, 17413, 17437, 17467, 17491, 17495, 17741, 17815, 17851, 17953
, 17969, 17971, 17993, 18001, 18011, 18053, 18079, 18157, 18221, 18223, 18345, 1
8381, 18545, 18551, 18565, 18607, 18641, 18653, 18689, 18737, 18799, 18877, 1892
9, 18979, 18985, 19049, 19059, 19077, 19087, 19127, 19189, 19207, 19229, 19231,
19247, 19327, 19331, 19347, 19349, 19357, 19397, 19423, 19441, 19487, 19501, 195
37, 19653, 19699, 19759, 19769, 19843, 19967]
answered Aug 11 at 23:51
Peter
45.3k939119
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
add a comment |Â
up vote
2
down vote
The expression $$varphi(n)^varphi(n)+n$$ is probable prime for $n=3113$ and $3157$ which are both composite. But for $n^n+varphi(n)$ I still do not know an example.
Smallest current candidate : $n=14 199$ ($58 958$ digits)
Candidates (no prime factor below $10^8$) :
[14199, 14227, 14231, 14237, 14253, 14295, 14363, 14381, 14479, 14485, 14501, 14
521, 14567, 14587, 14655, 14665, 14731, 14803, 14829, 14947, 14971, 14983, 15089
, 15091, 15133, 15179, 15191, 15199, 15203, 15281, 15307, 15331, 15391, 15411, 1
5415, 15481, 15505, 15509, 15535, 15573, 15701, 15739, 15821, 15917, 15919, 1596
7, 15999, 16003, 16021, 16059, 16063, 16157, 16213, 16291, 16295, 16483, 16511,
16541, 16543, 16545, 16565, 16583, 16603, 16615, 16617, 16635, 16711, 16717, 167
39, 16747, 16757, 16759, 16795, 16801, 16853, 16859, 16903, 16915, 16945, 16973,
17009, 17079, 17083, 17089, 17107, 17113, 17167, 17177, 17191, 17209, 17243, 17
377, 17383, 17411, 17413, 17437, 17467, 17491, 17495, 17741, 17815, 17851, 17953
, 17969, 17971, 17993, 18001, 18011, 18053, 18079, 18157, 18221, 18223, 18345, 1
8381, 18545, 18551, 18565, 18607, 18641, 18653, 18689, 18737, 18799, 18877, 1892
9, 18979, 18985, 19049, 19059, 19077, 19087, 19127, 19189, 19207, 19229, 19231,
19247, 19327, 19331, 19347, 19349, 19357, 19397, 19423, 19441, 19487, 19501, 195
37, 19653, 19699, 19759, 19769, 19843, 19967]
answered Aug 11 at 23:51
Peter
45.3k939119
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The expression $$varphi(n)^varphi(n)+n$$ is probable prime for $n=3113$ and $3157$ which are both composite. But for $n^n+varphi(n)$ I still do not know an example.
Smallest current candidate : $n=14 199$ ($58 958$ digits)
Candidates (no prime factor below $10^8$) :
[14199, 14227, 14231, 14237, 14253, 14295, 14363, 14381, 14479, 14485, 14501, 14
521, 14567, 14587, 14655, 14665, 14731, 14803, 14829, 14947, 14971, 14983, 15089
, 15091, 15133, 15179, 15191, 15199, 15203, 15281, 15307, 15331, 15391, 15411, 1
5415, 15481, 15505, 15509, 15535, 15573, 15701, 15739, 15821, 15917, 15919, 1596
7, 15999, 16003, 16021, 16059, 16063, 16157, 16213, 16291, 16295, 16483, 16511,
16541, 16543, 16545, 16565, 16583, 16603, 16615, 16617, 16635, 16711, 16717, 167
39, 16747, 16757, 16759, 16795, 16801, 16853, 16859, 16903, 16915, 16945, 16973,
17009, 17079, 17083, 17089, 17107, 17113, 17167, 17177, 17191, 17209, 17243, 17
377, 17383, 17411, 17413, 17437, 17467, 17491, 17495, 17741, 17815, 17851, 17953
, 17969, 17971, 17993, 18001, 18011, 18053, 18079, 18157, 18221, 18223, 18345, 1
8381, 18545, 18551, 18565, 18607, 18641, 18653, 18689, 18737, 18799, 18877, 1892
9, 18979, 18985, 19049, 19059, 19077, 19087, 19127, 19189, 19207, 19229, 19231,
19247, 19327, 19331, 19347, 19349, 19357, 19397, 19423, 19441, 19487, 19501, 195
37, 19653, 19699, 19759, 19769, 19843, 19967]
answered Aug 11 at 23:51
Peter
45.3k939119
The expression $$varphi(n)^varphi(n)+n$$ is probable prime for $n=3113$ and $3157$ which are both composite. But for $n^n+varphi(n)$ I still do not know an example.
Smallest current candidate : $n=14 199$ ($58 958$ digits)
Candidates (no prime factor below $10^8$) :
[14199, 14227, 14231, 14237, 14253, 14295, 14363, 14381, 14479, 14485, 14501, 14
521, 14567, 14587, 14655, 14665, 14731, 14803, 14829, 14947, 14971, 14983, 15089
, 15091, 15133, 15179, 15191, 15199, 15203, 15281, 15307, 15331, 15391, 15411, 1
5415, 15481, 15505, 15509, 15535, 15573, 15701, 15739, 15821, 15917, 15919, 1596
7, 15999, 16003, 16021, 16059, 16063, 16157, 16213, 16291, 16295, 16483, 16511,
16541, 16543, 16545, 16565, 16583, 16603, 16615, 16617, 16635, 16711, 16717, 167
39, 16747, 16757, 16759, 16795, 16801, 16853, 16859, 16903, 16915, 16945, 16973,
17009, 17079, 17083, 17089, 17107, 17113, 17167, 17177, 17191, 17209, 17243, 17
377, 17383, 17411, 17413, 17437, 17467, 17491, 17495, 17741, 17815, 17851, 17953
, 17969, 17971, 17993, 18001, 18011, 18053, 18079, 18157, 18221, 18223, 18345, 1
8381, 18545, 18551, 18565, 18607, 18641, 18653, 18689, 18737, 18799, 18877, 1892
9, 18979, 18985, 19049, 19059, 19077, 19087, 19127, 19189, 19207, 19229, 19231,
19247, 19327, 19331, 19347, 19349, 19357, 19397, 19423, 19441, 19487, 19501, 195
37, 19653, 19699, 19759, 19769, 19843, 19967]
answered Aug 11 at 23:51
Peter
45.3k939119
edited Aug 12 at 11:31
answered Aug 11 at 23:51
Peter
45.3k939119
answered Aug 11 at 23:51
Peter
45.3k939119
answered Aug 11 at 23:51
Peter
45.3k939119
45.3k939119
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
add a comment |Â
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
According to my calculations, there is no example for $nle 20 000$ in the case $n^n+varphi(n)$. Hence such an example must have more than $86 000$ digits,
– Peter
Aug 12 at 17:56
add a comment |Â
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%2f2879840%2fprimes-of-the-form-varphin-varphinn-or-nn-varphin-for-c%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
As usual, questions about primes of a given form receive at least one downvote :)
– Peter
Aug 12 at 12:03