Picking an odd prime $p|g$ (if it exists), we see that no such $n$ exists for both parts. Thus $g$ must be a power of two for both parts. Now pick an odd prime $p|(g-1)$, which exists as long as $g \neq 2$. We quickly get that no such $n$ works for such a prime $p$, so it follows $g=2$ is the only possible integer. Now note that: \[2^n \equiv n \pmod{p}\] \[\implies 2n \equiv n+1 \pmod{p}\] and thus $n \equiv 1 \pmod{p}$. Then $2^n \equiv 1 \pmod{p}$, and by CRT it is clear we can pick an $n$ which works (just do $n \equiv 0 \pmod{p-1}, 1 \pmod{p}$). This solves part a. as $g=2$ is the only possibility. For part b., note that \[2^n \equiv n^2 \pmod{p}\] \[2n^2 \equiv n^2 + 2n + 1 \pmod{p}\] \[(n-1)^2 \equiv 2 \pmod{p}\] which is impossible for $p=3$. Thus it follows for part b. no primes work.

A) $p|g^n-n \implies g^{n+1} \equiv n+1 \equiv gn \pmod{p} \implies n(g-1) \equiv 1 \pmod{p}$ for ever odd prime $p$. Then $g-1=2^m$ for some $m \in \mathbb{N_0}$. Then, unless $g=2$, $\exists$ odd $p \in \mathbb{P}$ such that $p|g$. But the, $g^n \equiv n \equiv 0 \pmod{p}$ and $g^{n+1} \equiv n+1 \equiv 0 \pmod{p} \implies n \equiv n+1 \pmod{p}$, a contradiction. So, $g=2$. Then $2^n \equiv n \pmod{p}$ and $2^{n+1} \equiv n+1 \pmod{p} \implies 2n \equiv n+1 \implies n \equiv 1 \equiv 2^n \pmod{p}$. And so, by using Chinese Remainder Theorem, $\exists n \equiv 0 \pmod{p-1}$ and $n \equiv 1 \pmod{p}$ since $(p,p-1)=1$. B) We proceed similarly. Firstly no odd prime $p$ may divide $g$. Then $g=2^m$. Also, we must have $p \nmid n$. Then using the notion of inverse modulos we get $g \equiv (\frac{n+1}{n})^2 \pmod{p} \forall$ odd primes $p$. Then $g$ must be a perfect square. So, $g=2^{2k}$. Take $p \in \mathbb{P}, p|g-1$. Then, $ \implies 2n+1 \equiv 0 \pmod{p} \implies n \equiv \frac{p-1}{2} \pmod{p} \implies n^2 \equiv 1 \equiv (\frac{p-1}{2})^2 \implies 1 \equiv 4 \pmod{p} \implies p=3 \implies 3^m+1=4^k \implies g=4$ which is a solution. Edit: Sorry for the wrong post, I corrected it now. Thanks, Kurt Godel for pointing out the flaw.

dinoboy wrote: For part b., note that \[2^n \equiv n^2 \pmod{p}\] \[2n^2 \equiv n^2 + 2n + 1 \pmod{p}\] \[(n-1)^2 \equiv 2 \pmod{p}\] which is impossible for $p=3$. Thus it follows for part b. no primes work. You only proved that $g = 2$ doesn't work for part b. What about other $g$? dibyo_99 wrote: B) ... So, $g=2^{2k}$. Then, we observe that $n \ncong 2 \pmod{3} \implies n \equiv 1 \pmod{3} \implies g \equiv 1 \pmod{3} \implies g=1$, but this is impossible. $g = 2^{2k}$ is true, but it is trivially congruent to 1 mod 3, so I don't understand how you conclude that $g=1$. Actually, to both of you, $g = 4$ is a solution to part (b).

Oh oops, this step was wrong. dinoboy wrote: Now pick an odd prime $p|(g-1)$, which exists as long as $g \neq 2$. We quickly get that no such $n$ works for such a prime $p$, so it follows $g=2$ is the only possible integer. I forgot the case when $1$ and $-1$ are actually consecutive modulo $p$. This occurs for $p=3$. Thus it follows the only odd prime divisor of $p$ is $3$, so it follows $g=4$ is force. Then to prove $g=4$ works we have $4^n - n^2 = (2^n - n)(2^n + n)$ and then use the same $n$ for part a.

dinoboy wrote: Oh oops, this step was wrong. dinoboy wrote: Now pick an odd prime $p|(g-1)$, which exists as long as $g \neq 2$. We quickly get that no such $n$ works for such a prime $p$, so it follows $g=2$ is the only possible integer. I forgot the case when $1$ and $-1$ are actually consecutive modulo $p$. This occurs for $p=3$. Thus it follows the only odd prime divisor of $p$ is $3$, so it follows $g=4$ is force. Then to prove $g=4$ works we have $4^n - n^2 = (2^n - n)(2^n + n)$ and then use the same $n$ for part a. Well, it is not immediate (but I agree it is not hard to prove) that $g = 4$; one needs to solve the equation $3^m + 1 = 2^n$, which actually was a problem in the South African olympiad of 1997. (It might also have appeared somewhere else or even be folklore, but this indicates that it's probably not trivial to participants. In the Belgian team only one student managed to arrive at this equation, but he was not able to solve it.)

Well taking modulo $3$ we arrive at $n$ is even, now just write $3^m = (2^a - 1)(2^a + 1)$. Since $\gcd(2^a - 1, 2^a + 1) = 1$ it follows they must both be powers of $3$, and thus one is $1$ and the other is $3$. I agree its nontrivial, but solving this diophantine equation is a very minor part of this problem.

Excuse me. can you explain these steps dibyo_99 wrote: Firstly no odd prime $p$ may divide $g$. Then $g=2^m$. Also, we must have $p \nmid n$. Then using the notion of inverse modulos we get $g \equiv (\frac{n+1}{n})^2 \pmod{p} \forall$ odd primes $p$. Then $g$ must be a perfect square.

Since $g$ is a quadratic residue $\pmod{p} \forall p$, we must have $g$ to be a perfect square. If you don't know this, you may try to prove it.

Hint