A more tricky problem was supposed to be in exam but this problem was selected so that the exam become easier: Let $k$ be a natural number such that $k\ge 7$ . How many $(x,y)$ such that $0\le x,y<2^k$ and $x,y$ be odd satisfy the equation $137^{137^{x^8+x}}\equiv 9^{9^{y^8+y}} \pmod {2^k}$?

hint

MahyarSefidgaran wrote: Let $k$ be a natural number such that $k\ge 7$. How many $(x,y)$ such that $0\le x,y<2^k$ and $x,y$ be odd satisfy the equation $137^{137^{x^8+x}}\equiv 9^{9^{y^8+y}} \pmod {2^k}$. I think the initial problem of Mahyar Sefidgaran is not harder than the problem posted by goodar2006. Both of them can be showed with the same method. BTW, they are very nice problems. . Here is a solution of mine. Let $v_2(x)$ be the exponent of $2$ in $x$, ie.. the largest natural number $a$ so that $2^a\mid x$. We shall use the Lifting The Exponent Lemma in our proof. Let $S$ be the set of all $137^{137^{x^8+x}}$ when $0\leq x<2^k$ and $x$ is odd. We have $|S|=2^{k-1}$. Lemma 1. Let $a$ be a non-negative, even, integer number. Then $137^{137^a}\equiv 9^{9^a}\equiv 137\equiv 9\pmod{2^7}$. The proof of Lemma 1 can be deduce easily from the Lifting The Exponent Lemma and the fact that $137=9+2^7$. Indeed, $v_2\left(137^{137^a}-137\right)=v_2(137-1)+v_2(137^a-1)=3+3+v_2(a)\geq 3+3+1=7$. The similar arguments can be applied for the rest. $\Box$ Lemma 2. For each $y$ such that $0\leq y<2^k$, $y$ is odd, there are exactly $2^6$ number $x$ with $0\leq x<2^k$ so that $137^{137^{x^8+x}}\equiv 137^{137^{y^8+y}}\pmod{2^k}$. Proof. Let $x,y$ be any odd number so that $0\leq x,y<2^k$ then $137^{137^{x^8+x}}\equiv 137^{137^{y^8+y}}\pmod{2^k}$ if and only if $2^k\mid 137^{137^{x^8+x}-137^{y^8+y}}-1$ iff $k\leq v_2\left(137^{137^{x^8+x}-137^{y^8+y}}-1\right)=v_2(137-1)+v_2(137^{x^8+x-y^8-y}-1)=3+3+v_2(x^8+x-y^8-y)=6+v_2(x-y)$. (Here we note that $\frac{x^8-y^8}{x-y}+1$ is an odd integer number for any integer odd numbers $x,y$.) So $137^{137^{x^8+x}}\equiv 137^{137^{y^8+y}}\pmod{2^k}$ iff $k-6\leq v_2(x-y)$ iff $2^{k-6}\mid x-y$. Now the interval $[0;2^k-1]$ is split into $2^6$ intevals which each of them has length $2^{k-6}$. For each odd number $y$ so that $0\leq y<2^k$, there are exactly $2^6$ number $x$ so that $2^{k-6}\mid x-y$ (each interval has exactly one such $x$). Lemma 2 is proven. $\Box$ The set $S$ has $2^{k-1}$ elements, it is divided into $2^6$ subsets $S_i$ ($1\leq i\leq 2^6$) so that, in each such subset, there are no two elements which are congruence in modulo $2^k$ (they are $[0;2^{k-6}-1]$, $[2^{k-6};2^{k-5}-1]$, $\ldots,[2^{k}-2-2^{k-6};2^k-1]$). For each $i$, $|S_i|=2^{k-7}$. From Lemma 1, for any $t\in S$ then $t\equiv 9\pmod{2^7}$. In each complete residue modulo $2^k$, there are exactly $2^{k}/2^{7}=2^{k-7}$ elements which iscongruent to $9$ modulo $2^7$. That is, each $S_i$ contains all elements which congruent to $9$ modulo $2^7$. Once again, from Lemma 1, $9^{9^{y^8+y}}\equiv 9\pmod {2^7}$. Hence, for each $y$ which is odd and $0\leq y<2^k$, then for each $i$, there is exactly one element in $S_i$ which is congruent to $9^{9^{y^8+y}}$ modulo $2^k$. So the number of solutions to the equation $137^{137^{x^8+x}}\equiv 9^{9^{y^8+y}} \pmod {2^k}$ is $2^6\times2^{k-1}=2^{k+5}$.

goodar2006 wrote: Let $k$ be a natural number such that $k\ge 7$. How many $(x,y)$ such that $0\le x,y<2^k$ satisfy the equation $73^{73^x}\equiv 9^{9^y} \pmod {2^k}$? proposed by Mahyar Sefidgaran As the above solution, we shall use the Lifting The Exponent Lemma in our proof. Lemma 1. $73^{73^a}\equiv 73\equiv 9\equiv 9^{9^a}\pmod{2^6}$ for any nonegative integer $a$. Proof. We have $73=9+2^6$ and $v_2\left(73^{73^a}-73\right)=v_2(73-1)+v_2(73^a-1)=6+v_2(a)\geq 6$. The rest is similar. $\Box$. Lemma 2. For each pair $(x,y)$, $0\leq x,y<2^k$, then $73^{73^x} \equiv73^{73^y}\pmod{2^k}$ if and only if $2^{k-6}\mid x-y$. Proof. Assume that $x\neq y$ and $73^{73^x} \equiv73^{73^y}\pmod{2^k}$. Then, $v_2\eft(73^{73^x} -73^{73^y}\right)=v_2(73-1)+v_2\left(73^{x-y}-1\right)=6+v_2(x-y)$. $\Box$. Let $S=\left\{73^{73^x}:\;0\leq x<2^k\right\}$ then $|S|=2^k$. By Lemma 2, we can find pairwise disjoint subsets $S_1,\ldots,S_{2^6}$ such that $\bigcup\limits_{i=1}^{2^6}S_i=S$ and for any $a,b\in S_i$ then $a\not\equiv b\pmod{2^k}$. We have $|S_i|=2^{k-6}$. From the Lemma 1, each element in $S_i$ is congruent to $9$ modulo $2^6$, and from the fact that, each complete residue system modulo $2^k$, has exactly $2^{k-6}$ elements which is congruent to $9$ modulo $2^6$. So for each $i=1,\ldots,2^6$ then $S_i$ contains all number which is congruent to $9$ modulo $2^6$. Each $y$ so that $0\leq y<2^k$, and each $i=1,\ldots,2^{6}$ there is exactly one $x$, $0\leq x<2^k$, so that $73^{73^x}\equiv 9^{9^y}\pmod {2^k}$. So the number of solutions to the equation $73^{73^x}\equiv 9^{9^y} \pmod {2^k}$ is $2^k\times 2^6=2^{k+6}$.

pluricomplex wrote: goodar2006 wrote: Let $k$ be a natural number such that $k\ge 7$. How many $(x,y)$ such that $0\le x,y<2^k$ satisfy the equation $73^{73^x}\equiv 9^{9^y} \pmod {2^k}$? proposed by Mahyar Sefidgaran As the above solution, we shall use the Lifting The Exponent Lemma in our proof. Lemma 1. $73^{73^a}\equiv 73\equiv 9\equiv 9^{9^a}\pmod{2^6}$ for any nonegative integer $a$. Proof. We have $73=9+2^6$ and $v_2\left(73^{73^a}-73\right)=v_2(73-1)+v_2(73^a-1)=6+v_2(a)\geq 6$. The rest is similar. $\Box$. Lemma 2. For each pair $(x,y)$, $0\leq x,y<2^k$, then $73^{73^x} \equiv73^{73^y}\pmod{2^k}$ if and only if $2^{k-6}\mid x-y$. Proof. Assume that $x\neq y$ and $73^{73^x} \equiv73^{73^y}\pmod{2^k}$. Then, $v_2\left(73^{73^x} -73^{73^y}\right)=v_2(73-1)+v_2\left(73^{x-y}-1\right)=6+v_2(x-y)$. $\Box$. Let $S=\left\{73^{73^x}:\;0\leq x<2^k\right\}$ then $|S|=2^k$. By Lemma 2, we can find pairwise disjoint subsets $S_1,\ldots,S_{2^6}$ such that $\bigcup\limits_{i=1}^{2^6}S_i=S$ and for any $a,b\in S_i$ then $a\not\equiv b\pmod{2^k}$. We have $|S_i|=2^{k-6}$. From the Lemma 1, each element in $S_i$ is congruent to $9$ modulo $2^6$, and from the fact that, each complete residue system modulo $2^k$, has exactly $2^{k-6}$ elements which is congruent to $9$ modulo $2^6$. So for each $i=1,\ldots,2^6$ then $S_i$ contains all number which is congruent to $9$ modulo $2^6$. Each $y$ so that $0\leq y<2^k$, and each $i=1,\ldots,2^{6}$ there is exactly one $x$, $0\leq x<2^k$, so that $73^{73^x}\equiv 9^{9^y}\pmod {2^k}$. So the number of solutions to the equation $73^{73^x}\equiv 9^{9^y} \pmod {2^k}$ is $2^k\times 2^6=2^{k+6}$.