Suppose there are C, D such that n|2^C +3^D . Then gcd(n,6)=1, so 2^C=-3^D (mod n) so 2^C*3^(phi(n)-d)=-1 mod n, contradiction

its so izi

random314 wrote: Suppose there are C, D such that n|2^C +3^D . Then gcd(n,6)=1, so 2^C=-3^D (mod n) so 2^C*3^(phi(n)-d)=-1 mod n, contradiction Why $gcd(n,6)=1$?

A-Thought-Of-God wrote: Why $gcd(n,6)=1$? otherwise, if $3$ $\mid$ $n$ $\implies$ $2^n$ $\equiv$ $0$ $\pmod{3}$. Clearly, $2^n+3^n$ is odd, so $\gcd (n,6)=1$

suppose there exists $c,d$ such that$n|2^c+3^d$ then $2^c \equiv -3^d mod$ $n$ we have $2^c3^b+1=1-3^{b+d}$ is not divisible by $n$ for any $b \in N$ put $b=k.\phi(n)-d$ for large enough $k$ then $1-3^{k.\phi(n)} \equiv 0 mod$ $n $ a contradiction

FTSOC assume that $\exists \hspace{.05 cm} n$ s.t. we can find $c,d$ satisfying $2^c+3^d \equiv{0} \pmod{n}$. We have $3^d \equiv{-2^c} \pmod{n}$. Now I claim that choosing $a=k\phi(n)-c$ and $b=d+k\phi(n)$ for large enough natural $k$ contradicts, i.e.$n \mid 2^a3^b+1$. Since $k$ is large enough, assume $b>d$. Note thata $3^b \equiv{-3^{b-d}2^c} \pmod{n}$ so $2^a3^b \equiv{-3^{b-d}2^{a+c}} \equiv{-3^{k\phi(n)} \cdot 2^{k\phi(n)}} \equiv{-1} \pmod{n}$ since $(n,6)=1$ (or else $2 \text{ or } 3 \mid 2^a+3^b$)

Quite similar with other solutions, but with little different path: Assume the contrary. Note that for $n$ to divide $2^{c}+3^{d}$ $n$ must be coprime with both $2$ and $3$ ($n$ cannot be $1$ for obvious reasons). Thus $2^{\varphi(n)} \equiv 3^{\varphi(n)} \equiv 1$ (mod $n$) where $\varphi$ represents Euler's totient function. Let $x$ be a positive integer such that $x\varphi(n) \geq c$. Then we get $0 \equiv 2^{c}+3^{d} \equiv 2^{c}+3^{d}2^{x\varphi(n)} \equiv 2^{c}(2^{(x\varphi(n)-c)}3^{d}+1) \equiv 2^{(x\varphi(n)-c)}3^{d}+1 \equiv 2^{a}3^{b}+1 \equiv 0$ (mod $n$) since $n \nmid 2^{c}$. Contradiction.

What is this zhautykov anyway? Clearly if $(2,n) \not=1$ Then $2 \not |2^a+3^b ,\implies n \not | 2^a+3^b$ and similarly this holds for $3$ too. If $(n,2)=(n 3)=1$,then FTSOC assume $n|2^c+3^d$ This implies $2^c\equiv -3^d \equiv -3^d.3^{-k\phi(n)} \pmod n (k \geq d) $ Which inturn gives $2^c.3^{k\phi(n)-d} \equiv -1 \pmod n$ which is a contradiction $\blacksquare$

What if, phi(n)<d

Obviously $\gcd(n, 6) = 1$. Now $$2^a3^b \not \equiv -1 \pmod n \iff 2^a \not \equiv -\left(\frac 13\right)^b \equiv -3^{b(k-1)} \pmod n$$where $k$ is the order of $3$ mod $n$. By varying $b$, this means that $2^c \not \equiv -3^d \pmod n$ for all $(c, d)$, which yields the result.

$n=529$ is an example that shows the problem is not vacuous (i.e. there exists an $n$ with $n \perp 6$ such that $2^a 3^b \not\equiv -1 \pmod{n}$ for all $(a,b)$.

Notice that $a$ and $b$ are up to our choosing. Suppose FTSOC that $2^c+3^d\equiv 0$ (mod $n$) even though $2^a3^b+1$ is always not divisible by $n$. Pick $c=a$, then $2^c\equiv -3^d$ so $3^{b+d}$ is never $1$ mod $n$. This is clearly false, since we assumed $2^c+3^d\equiv 0$ (implying that $2, 3\nmid n$ or that $\gcd(3, n)=1$) and we can choose $b$. So we are done. $\blacksquare$

Note that if $n$ is a multiple of $6$, then we are done. This is because if either of $c$, $d$ are greater than $1$, then the sum $2^c+3^d$ is relatively prime to either $2$ or $3$, proving the claim. Otherwise, $n$ must be relatively prime to either $2$ or $3$. If $n$ is relatively prime to $3$, then note that for every ordered pair $(c,d)$ there must be some number $k$ such that $3^{d+k}$ is $1$ mod $n$. FTSOC, assume there is an ordered pair $(c,d)$ such that $n\mid 2^c+3^d$. Therefore we would have that \[0\equiv 2^c+3^d \equiv 2^c3^k+3^{d+k}\equiv2^c3^k +1 \pmod{n},\]which implies that $n\mid 2^c3^k+1$, a contradiction by the given condition. Therefore $n$ cannot divide any $2^c+3^d$. Doing this similarly for if $n$ is relatively prime to $2$, we get the same thing, finishing the problem.

FTSOC, assume that $n|(2^c+3^d)$. Then $2\not| n$ and $3\not| n$ so $\gcd(n, 6)=1$. Since $2^c\equiv -3^d\pmod{n}$, $2^c3^{\phi(n)-d}\equiv -1\pmod{n}$, finishing our contradiction. Therefore, $n\not|(2^c+3^d)$.

If $n$ is not relatively prime to $2$ or $3$, the problem is vacuous. Otherwise, $\gcd(n,6)=1$. FTSOC assume $2^c+3^d$ is divisible by $n$. We have \[2^c \equiv -3^d \pmod{n}\]\[\implies 2^c3^{\varphi(n)-d} \equiv -1 \pmod{n},\] a contradiction. $\square$

Assume the contrary, i.e. there exist natural numbers $c$ and $d$ such that $$n\mid 2^c+3^d \iff 2^c\equiv -3^d\pmod{n}.$$Note that if $2\mid n$, we get $2\mid 3^d$, a contradiction. Therefore, $\gcd(n,2)=1$ and similarly $\gcd(n,3)=1$. Now pick $a=c$ and we get $$2^a3^b+1\equiv -3^d\cdot3^b+1 \pmod{n}.$$However, from Euler we have $$3^{\varphi(n)}\equiv1\pmod{n} \Rightarrow 3^{m\varphi(n)}\equiv1\pmod{n},$$where $m$ is a positive integer. Hence, if we pick $b=m\varphi(n)-d$ for a sufficiently large $m$ (in this way we ensure $b$ to be a positive integer), we get $$2^a3^b+1\equiv-3^d\cdot3^b+1 \equiv -3^{m\varphi(n)}+1 \equiv-1+1\equiv 0\pmod{n},$$which is a contradiction and we are done.

Clearly if $\operatorname{gcd}(n,3)$ or $\operatorname{gcd}(n,2) > 1$, then such an $n$ satisfies. Now we work with the rest of $n$ where $\operatorname{gcd}(n,3)=\operatorname{gcd}(n,2)=1$. FTSOC assume $n\mid 2^{c_0} + 3^{c_0} \implies 2^{c_0}\equiv -3^{d_0}\pmod{n} \implies 2^{c_0}\cdot 3^{-d_0} \equiv -1 \pmod{n}$. Now pick a $k$ such that $k \cdot \operatorname{ord}_{n}(3)>d_0$. Thus we get that $n \mid 2^{c_0} \cdot 3^{-d_0}\cdot 3^{k(\operatorname{ord}_{n}(3))}+1 \implies n \mid 2^{c_0}\cdot3^{k(\operatorname{ord}_{n}(3)) - d_0} + 1$ which is a contradiction.

The problem is trivial if $3\mid n$. Now if $3\nmid n$: using the fact that $3^{\phi(n)} \equiv 1 \pmod{n}$ gives us: $$(2^c+3^d)\cdot 3^{\phi(n)-d}\equiv 2^c3^{\phi(n)-d}+1 \not\equiv 0 \pmod{n} $$ Which ends the problem. $$\mathbb{Q.E.D.}$$

We will prove the contrapositive that if there exists some naturals $c,d$ such that $n \mid 2^c+3^d$ then there exists some naturals $a,b$ such that $n \mid 2^a3^b+1$. Note from the first part of the statement we have that $2^c \equiv -3^d \mod{n}$. Clearly $\gcd(n,2,3)=1$. Then let us have $a=c$, we then have $-3^{b+d}+1 \equiv 0 \mod{n} \implies 3^{b+d} \equiv 1 \mod {n}$. Now we can pick $b=t\varphi(n)-d$ where $t$ is a constant such that $t\varphi(n) > d$.

why so izi Assume that there exists $n$ such that $n \mid 2^c + 3^d$ for some $c, d$, and $n \nmid 2^a\cdot3^b + 1$. We may assume $(n, 6) = 1$, and if it's not we're done since then $n \nmid 2^c + 3^d$. So, pick $b = d$, and $2^a \cdot 3^b \equiv -2^{a + c} + 1 \mod{n}$. However, simply picking $a = k\phi(n) - c$, gives us a contradiction, so we're done.

For the sake of a contradiction, suppose that $c, d$ existed. Then $2^c\equiv -3^d \pmod n.$ Therefore, letting $b=d$ gives $2^{a+c} \equiv 1 \pmod {n}.$ Since order exists, for this to never hold it follows that $2|n.$ But then, $2^c+3^d \equiv 0 \pmod n \implies 0 \equiv 2^c+3^d \equiv 1 \pmod 2,$ a contradiction. QED