2

For this question, I have tried to start from reading similar question (How many rationals of the form $\frac{2^n+1}{n^2}$ are integers? from this post How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers?)

I notice that $2^{2!}-1$ is always odd so I tried to rewrite it as $2k+1$ but I am stuck afterward. I am thinking of how do I relate this to modular arithmetic or gcd. I would appreciate if anyone could help.

HTLL
  • 225
  • 1
  • 7
  • 1
    Where does the question come from? – Igor Rivin Apr 17 '21 at 03:34
  • Our math professor left this for us as a practice for learning problem solving skills for math competition. – HTLL Apr 17 '21 at 03:43
  • 2
    It has the air of a contest problem all right. But what kind of a school expects their students to participate in math competitions? Sorry to sound a bit rude, but in the past we have had students who try to cheat in contests by asking for help here. – Jyrki Lahtonen Apr 17 '21 at 03:44
  • @JyrkiLahtonen I am a bit out of the contest loop, but are there many "take-home" contests these days? Since that is the only context where asking here is usefull. – Igor Rivin Apr 17 '21 at 03:49
  • I don't know for sure either @IgorRivin. There are many contests where a preliminary round is take-home. I guess most of them have later rounds designed partly to catch cheaters. Even pre-pandemic. Also, one organizer told me that they have no trouble whatsoever singling out internet copycats from the entrants :-) – Jyrki Lahtonen Apr 17 '21 at 03:54
  • 1
    We are taking a class which is all about solving IMO or Putnam problems. – HTLL Apr 17 '21 at 03:54
  • That is rather exceptional. Why would any normal school have such a class? I can imagine a teacher running a club dedicated to contest math somewhere for fun, but an official class? – Jyrki Lahtonen Apr 17 '21 at 03:58
  • This is a class for master's degree. We are trained to solve those problems so we can create our own questions for our students. – HTLL Apr 17 '21 at 03:58
  • @JohnOmielan Oh you are right, let me edit it – HTLL Apr 17 '21 at 04:01
  • Well, $n^2+1$ can not be even, otherwise $2 \mid -1$. Thus $\gcd(n^2+1,2)=1$ and $2^{\varphi(n^2+1)}\equiv 1\pmod{n^2+1}$ from the Euler's theorem. Now, see if you can extend this, by borrowing a few ideas from here. – rtybase Apr 17 '21 at 08:26
  • It can be shown that if m is odd then it divides $2^{n!}-1$. Hence n must be even to make $n^2+1$ odd. – sirous Apr 17 '21 at 14:33

1 Answers1

1

In the link in comment it is proved that $m^2-1\big|2^{m!}-1$ . Let $m=n^2$, then $m^2-1=n^4-1\big|2^{m!=n^2!}-1$ and $n^2+1\big|(n^4-1)$. For example :

$n=4 \rightarrow 4^2+1=17\big|4^4-1$ and we have:

$2^{4!}-1=2^{24}-1=[(2^4)^3-1][(2^4)^3+1]$

$(2^4)^3+1=(2^4+1)[(2^4)^2-(2^4)+1]=17k$

therefore:

$4^2+1\big|2^{4!}-1$

In fact $n=4$ is the smallest number and general form of n is $2t$ such that $(2t)^2+1$ is a prime. Another example:

$10^2+1=101\rightarrow 2^{101}\equiv 1 \bmod 101$, $100!=100(s)$ and $2^{100!}=(2^{100})^s\equiv 1 \bmod 101\Rightarrow 10^2+1\big|2^{100!}-1$.

sirous
  • 10,751
  • Note with $n = 6$, then $n^2 + 1 = 37$. By Fermat's little theorem, $37 \mid 2^{36} - 1 \implies 2^{36} \equiv 1 \pmod{37}$. Also, $6! = 720 = 36(20)$. Thus, $2^{720} \equiv (2^{36})^{20} \equiv 1 \pmod{37} \implies 37 \mid 2^{6!} - 1$. – John Omielan Apr 17 '21 at 19:31
  • @JohnOmielan, thanks for reasoning for 6. So the condition can be that n must be even., is that right? – sirous Apr 18 '21 at 03:34
  • 1
    You're welcome. As for the condition, yes $n$ must be even but, also, it's required that the multiplicative order of $2$ modulo $n^2 + 1$ divides $n!$, i.e., $\operatorname{ord}_{n^2 + 1} \mid n!$. This will include almost all even $n$ (I haven't bothered determining any exceptions, although I'm confident they're there), including those where $n^2 + 1$ is not prime, e.g., $n = 8 \implies n^2 + 1 = 65 = 5(13)$. I suspect the OP and/or their professor made a mistake, e.g., where $n^2 + 1$ should be $n^2 - 1$, like in the proposed duplicate. – John Omielan Apr 18 '21 at 04:11