Fdtxjr

Official degrees of earth’s rotation per day

Have the tides ever turned twice on any open problem?

This word with a lot of past tenses

What is the relationship between relativity and the Doppler effect?

How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?

Aluminum electrolytic or ceramic capacitors for linear regulator input and output?

World War I as a war of liberals against authoritarians?

Are Roman Catholic priests ever addressed as pastor

ERC721: How to get the owned tokens of an address

Python if-else code style for reduced code for rounding floats

Why one should not leave fingerprints on bulbs and plugs?

Why does overlay work only on the first tcolorbox?

Is there a place to find the pricing for things not mentioned in the PHB? (non-magical)

Min function accepting varying number of arguments in C++17

PTIJ: Who should I vote for? (21st Knesset Edition)

The German vowel “a” changes to the English “i”

Professor being mistaken for a grad student

How can we have a quark condensate without a quark potential?

How could an airship be repaired midflight?

Is "upgrade" the right word to use in this context?

What exactly is this small puffer fish doing and how did it manage to accomplish such a feat?

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Why Choose Less Effective Armour Types?

What did “the good wine” (τὸν καλὸν οἶνον) mean in John 2:10?

A006517: Numbers with $nmid 2^n+2$

Understanding the proof that if $nmid 2^n+2$ and $n>1$, then $n$ is evenWhen is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?If $3mid a,b,c$ and $n=a^2+b^2+c^2$, prove that there exist $x,y,z$ such that $n=x^2+y^2+z^2$, where $3nmid x,y,z$.Generalized taxicab numbers: pairs of squaresHow to show infinite square-free numbers?Is always two times an even semiprime at a distance $1$ or prime to the closest previous odd semiprime?What is the series of numbers, where each number is a triangular, square, and hexagonal number?Deductions about the prime factorization of odd integers $m>1$ satisfying $frac-3+sqrt1+8m2=prod_substackpmid m\ptext prime(p-1)$Finishing the task to find the solutions of $frac1x-frac1y=frac1varphi(xy),$ where $varphi(n)$ denotes the Euler's totient functionOn prime-perfect numbers and the equation $fracvarphi(n)n=fracvarphi(operatornamerad(n))operatornamerad(sigma(n))$Odd numbers with $varphi(n)/n < 1/2$

6

3

$begingroup$

Problem 323 from the IMO 2009 reads:

Prove that there are infinitely many positive integers n such that $2^n+2$ is divisible by $n$.

An amazingly nice (and short) solution can be found here (see page 3).

OEIS sequence A006517 lists the 27 smallest integers $n$ with $nmid 2^n+2$:
$$ 1, 2, 6, 66, 946, 8646, 180246, 199606, 265826, 383846, 1234806, 3757426, 9880278, 14304466, 23612226, 27052806, 43091686, 63265474, 66154726, 69410706, 81517766, 106047766, 129773526, 130520566, 149497986, 184416166, 279383126. $$

All these numbers, with the exception of $1$, are even, and Max Alekseyev has shown that this keeps to hold for larger terms, too: if $nmid 2^n+2$ and $n>1$, then $n$ is even.

Yet another observation is that all numbers listed above are square-free. Does this hold in general?

Is it true that if $nmid 2^n+2$, then $n$ is square-free?

elementary-number-theory divisibility

share|cite|improve this question

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  A not squarefree example must exceed $large 10^15$
  $endgroup$
  – Peter
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Still no not squarefree solution upto $large 10^16$
  $endgroup$
  – Peter
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Peter: We know that a counterexample must be divisible by $2p^2$, where $p$ is a Wieferich prime. On the other hand, $2^nequiv -2pmod p$, along with the fact that $n$ is even, shows that any odd prime $p$ dividing $n$ satisfies $(-2/p)=1$. Since there are only two Wieferich primes below $10^17$, and none of them satisfies this condition, any counterexample must exceed $2cdot 10^34$.
  $endgroup$
  – W-t-P
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Good observation !
  $endgroup$
  – Peter
  20 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What does $(-2/p)=1$ mean?
  $endgroup$
  – mbjoe
  20 hours ago
  

  
  
  
  

 | 
show 3 more comments

6

3

$begingroup$

Problem 323 from the IMO 2009 reads:

Prove that there are infinitely many positive integers n such that $2^n+2$ is divisible by $n$.

An amazingly nice (and short) solution can be found here (see page 3).

OEIS sequence A006517 lists the 27 smallest integers $n$ with $nmid 2^n+2$:
$$ 1, 2, 6, 66, 946, 8646, 180246, 199606, 265826, 383846, 1234806, 3757426, 9880278, 14304466, 23612226, 27052806, 43091686, 63265474, 66154726, 69410706, 81517766, 106047766, 129773526, 130520566, 149497986, 184416166, 279383126. $$

All these numbers, with the exception of $1$, are even, and Max Alekseyev has shown that this keeps to hold for larger terms, too: if $nmid 2^n+2$ and $n>1$, then $n$ is even.

Yet another observation is that all numbers listed above are square-free. Does this hold in general?

Is it true that if $nmid 2^n+2$, then $n$ is square-free?

elementary-number-theory divisibility

share|cite|improve this question

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  A not squarefree example must exceed $large 10^15$
  $endgroup$
  – Peter
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Still no not squarefree solution upto $large 10^16$
  $endgroup$
  – Peter
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Peter: We know that a counterexample must be divisible by $2p^2$, where $p$ is a Wieferich prime. On the other hand, $2^nequiv -2pmod p$, along with the fact that $n$ is even, shows that any odd prime $p$ dividing $n$ satisfies $(-2/p)=1$. Since there are only two Wieferich primes below $10^17$, and none of them satisfies this condition, any counterexample must exceed $2cdot 10^34$.
  $endgroup$
  – W-t-P
  yesterday
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Good observation !
  $endgroup$
  – Peter
  20 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What does $(-2/p)=1$ mean?
  $endgroup$
  – mbjoe
  20 hours ago
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

Problem 323 from the IMO 2009 reads:

Prove that there are infinitely many positive integers n such that $2^n+2$ is divisible by $n$.

An amazingly nice (and short) solution can be found here (see page 3).

OEIS sequence A006517 lists the 27 smallest integers $n$ with $nmid 2^n+2$:
$$ 1, 2, 6, 66, 946, 8646, 180246, 199606, 265826, 383846, 1234806, 3757426, 9880278, 14304466, 23612226, 27052806, 43091686, 63265474, 66154726, 69410706, 81517766, 106047766, 129773526, 130520566, 149497986, 184416166, 279383126. $$

All these numbers, with the exception of $1$, are even, and Max Alekseyev has shown that this keeps to hold for larger terms, too: if $nmid 2^n+2$ and $n>1$, then $n$ is even.

Yet another observation is that all numbers listed above are square-free. Does this hold in general?

Is it true that if $nmid 2^n+2$, then $n$ is square-free?

elementary-number-theory divisibility

share|cite|improve this question

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

$endgroup$

share|cite|improve this question

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

share|cite|improve this question

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

asked Mar 12 at 10:42

W-t-PW-t-P

1,424612

1 Answer
1

active

oldest

votes

3

$begingroup$

Just an observation. If we assume $n=qcdot p^2$ where $p$ is an odd prime number, then
$$2^n equiv -2 pmodp^2 tag1$$
and from Euler's theorem
$$2^varphileft(p^2right) equiv 1 pmodp^2 iff
2^p(p-1) equiv 1 pmodp^2 tag2$$
Expanding $(2)$ we have
$$2^p^2(p-1) equiv 1^p pmodp^2 Rightarrow
2^qcdot p^2 cdot (p-1) equiv 1^q pmodp^2 Rightarrow \
2^n cdot (p-1) equiv 1 pmodp^2 tag3$$
but, from $(1)$ and given $p-1$ is even
$$2^ncdot(p-1) equiv (-2)^p-1 equiv 2^p-1 pmodp^2 tag4$$
combining $(3)$ and $(4)$
$$2^p-1 equiv 1 pmodp^2$$
which makes $p$ a Wieferich prime (also here), of which only two are known so far, $1093$ and $3511$ (A001220).

share|cite|improve this answer

answered 2 days ago

rtybasertybase

11.5k31534

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I found that out independent from your post (+1). I did not find a squarefree example yet, but it must be greater than $10^13$. One slight remark : $n$ cannot be divisible by $4$, so we actually can conclude that $p^2mid n$ is only possible for odd prime $p$
  $endgroup$
  – Peter
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @rtybase: Good point!
  $endgroup$
  – W-t-P
  yesterday
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3144926%2fa006517-numbers-with-n-mid-2n2%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

Just an observation. If we assume $n=qcdot p^2$ where $p$ is an odd prime number, then
$$2^n equiv -2 pmodp^2 tag1$$
and from Euler's theorem
$$2^varphileft(p^2right) equiv 1 pmodp^2 iff
2^p(p-1) equiv 1 pmodp^2 tag2$$
Expanding $(2)$ we have
$$2^p^2(p-1) equiv 1^p pmodp^2 Rightarrow
2^qcdot p^2 cdot (p-1) equiv 1^q pmodp^2 Rightarrow \
2^n cdot (p-1) equiv 1 pmodp^2 tag3$$
but, from $(1)$ and given $p-1$ is even
$$2^ncdot(p-1) equiv (-2)^p-1 equiv 2^p-1 pmodp^2 tag4$$
combining $(3)$ and $(4)$
$$2^p-1 equiv 1 pmodp^2$$
which makes $p$ a Wieferich prime (also here), of which only two are known so far, $1093$ and $3511$ (A001220).

share|cite|improve this answer

answered 2 days ago

rtybasertybase

11.5k31534

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I found that out independent from your post (+1). I did not find a squarefree example yet, but it must be greater than $10^13$. One slight remark : $n$ cannot be divisible by $4$, so we actually can conclude that $p^2mid n$ is only possible for odd prime $p$
  $endgroup$
  – Peter
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @rtybase: Good point!
  $endgroup$
  – W-t-P
  yesterday
  

  
  
  
  

add a comment | 

3

$begingroup$

Just an observation. If we assume $n=qcdot p^2$ where $p$ is an odd prime number, then
$$2^n equiv -2 pmodp^2 tag1$$
and from Euler's theorem
$$2^varphileft(p^2right) equiv 1 pmodp^2 iff
2^p(p-1) equiv 1 pmodp^2 tag2$$
Expanding $(2)$ we have
$$2^p^2(p-1) equiv 1^p pmodp^2 Rightarrow
2^qcdot p^2 cdot (p-1) equiv 1^q pmodp^2 Rightarrow \
2^n cdot (p-1) equiv 1 pmodp^2 tag3$$
but, from $(1)$ and given $p-1$ is even
$$2^ncdot(p-1) equiv (-2)^p-1 equiv 2^p-1 pmodp^2 tag4$$
combining $(3)$ and $(4)$
$$2^p-1 equiv 1 pmodp^2$$
which makes $p$ a Wieferich prime (also here), of which only two are known so far, $1093$ and $3511$ (A001220).

share|cite|improve this answer

answered 2 days ago

rtybasertybase

11.5k31534

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I found that out independent from your post (+1). I did not find a squarefree example yet, but it must be greater than $10^13$. One slight remark : $n$ cannot be divisible by $4$, so we actually can conclude that $p^2mid n$ is only possible for odd prime $p$
  $endgroup$
  – Peter
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @rtybase: Good point!
  $endgroup$
  – W-t-P
  yesterday
  

  
  
  
  

add a comment | 

$begingroup$

Just an observation. If we assume $n=qcdot p^2$ where $p$ is an odd prime number, then
$$2^n equiv -2 pmodp^2 tag1$$
and from Euler's theorem
$$2^varphileft(p^2right) equiv 1 pmodp^2 iff
2^p(p-1) equiv 1 pmodp^2 tag2$$
Expanding $(2)$ we have
$$2^p^2(p-1) equiv 1^p pmodp^2 Rightarrow
2^qcdot p^2 cdot (p-1) equiv 1^q pmodp^2 Rightarrow \
2^n cdot (p-1) equiv 1 pmodp^2 tag3$$
but, from $(1)$ and given $p-1$ is even
$$2^ncdot(p-1) equiv (-2)^p-1 equiv 2^p-1 pmodp^2 tag4$$
combining $(3)$ and $(4)$
$$2^p-1 equiv 1 pmodp^2$$
which makes $p$ a Wieferich prime (also here), of which only two are known so far, $1093$ and $3511$ (A001220).

share|cite|improve this answer

answered 2 days ago

rtybasertybase

11.5k31534

$endgroup$

share|cite|improve this answer

answered 2 days ago

rtybasertybase

11.5k31534

answered 2 days ago

rtybasertybase

11.5k31534

answered 2 days ago

rtybasertybase

11.5k31534