0
$\begingroup$

My approach for this question is to use Chinese remainders theorem. First to calculate $ x^{23^{33}}\bmod{7} $and then $ x^{23^{33}}\bmod {11}$. However, I don't know how to solve $ x^{23^{33}}\bmod 7$.

$\endgroup$
7
  • 1
    $\begingroup$ Please use MathJax to typeset mathematics. Here's a tutorial $\endgroup$ Apr 14, 2021 at 16:23
  • $\begingroup$ Welcome to MSE. in order for MathJax commands to be effective, they must be enclosed in$ signs. For example, $x^2$ shows up as $x^2$. $\endgroup$
    – saulspatz
    Apr 14, 2021 at 16:23
  • 3
    $\begingroup$ Exponentiation is not associative. Do you mean $13^{23^{33}}$ or $\left(13^{23}\right)^{33}$? $\endgroup$
    – saulspatz
    Apr 14, 2021 at 16:25
  • 2
    $\begingroup$ Please don't change your question after answers have been posted. $\endgroup$ Apr 14, 2021 at 16:46
  • 1
    $\begingroup$ @BillDubuque: I now understood the mismatch between question and answers. I think such edits should be rolled back. $\endgroup$
    – Paramanand Singh
    Apr 14, 2021 at 16:50

3 Answers 3

1
$\begingroup$

Hint: Observe that $23^{33}$ is odd, and that:

$$13^{2k} \equiv (-1)^{k} \mod 7$$

For any integer $k$.

And for any other possibility, we have that:

$$13^j \equiv 6 \equiv -1\mod 7$$

for any odd $j$, observe that, by definition, $7 | 6 - (-1)$.

$\endgroup$
3
  • 1
    $\begingroup$ To get the parenthetical "mod", use \pmod{7} instead of \mod 7: $13^{2k}\equiv (-1)^k\pmod{7}$ gives $13^{2k}\equiv (-1)^k\pmod{7}$. To get the binary mod operator, use \bmod (which does not include the awkward extra spacing: compare $-1\mod 7$: $-1 \mod 7$, with $-1\bmod 7$: $-1\bmod 7$. $\endgroup$ Apr 14, 2021 at 16:53
  • $\begingroup$ Thanks, I will make use of them from now on. $\endgroup$ Apr 14, 2021 at 16:57
  • $\begingroup$ ones for binary operation mod, and ones for relational mod. $\endgroup$ Apr 14, 2021 at 23:40
1
$\begingroup$

Let's try using the Carmichael reduced totient $\lambda$, iterated for the second exponent, to find a simpler expression:

$$ x^{\large 23^{\Large 33}} \equiv x^{\large (23^{\Large 33\bmod \lambda(\lambda(77))} \bmod \lambda(77))}\bmod 77$$

$\lambda(77)=\text{lcm}(\lambda(7),\lambda(11))=\text{lcm}(6,10) = 30$
$\lambda(30)=\text{lcm}(\lambda(2),\lambda(3),\lambda(5)) = 4$

So we don't get anything out of the first exponent reduction, but the second gives us $33\equiv 1 \bmod 4$. Reducing an exponent to $1$ is sometimes a little problematic but here $23$ is prime and large enough not to be an issue so we can say (for $x\in \Bbb N$):

$$x^{\large 23^{\Large 33}} \equiv x^{23}\bmod 77$$

$\endgroup$
3
  • 1
    $\begingroup$ Carmichael only applies if $x$ is coprime to $77$ so the argument is incomplete (or incorrect). In any case, it is a dupe. $\endgroup$ Apr 14, 2021 at 18:32
  • $\begingroup$ No Bill, Carmichael applies all the time as the minimum & universal cycle length. Some care may need to be applied when reducing to low exponent values is the only caveat, but there are no prime powers of exponent over $23$ in $77$. Is this a dupe? I'm not sure I've seen this kind of question with a variable base. $\endgroup$
    – Joffan
    Apr 14, 2021 at 18:37
  • 1
    $\begingroup$ Please precisely state the (Carmichael) Theorem that you are implicitly applying above. The most common version only applies when $x$ is coprime to the modulus. In a question at this level one should always be more precise, and justify such claims by linking to proofs, since there are frequently oversights in such matters. $\endgroup$ Apr 14, 2021 at 18:44
0
$\begingroup$

A consequence of Euler's theorem is that when you reduce $a^b$ modulo $n$ where $a$ and $n$ are coprime, you can reduce the exponent $b$ modulo $\varphi(n)$, where $\varphi$ is Eulers totient function: $$ b\equiv c \pmod{\varphi(n)} \quad\Longrightarrow\quad a^b \equiv a^c \pmod{n}. $$ You can apply that recursively to reduce towers of powers.

$\endgroup$
2
  • $\begingroup$ But this does not apply in the OPs case since $x$ is not assumed coprime to $77\ $ (after edit) $\endgroup$ Apr 14, 2021 at 16:45
  • $\begingroup$ @BillDubuque Right, … When I answered it was $13$ instead of $x$. $\endgroup$
    – Christoph
    Apr 14, 2021 at 18:18

Not the answer you're looking for? Browse other questions tagged .