1
$\begingroup$

Find $x$, such that $$x^{98} \equiv 7 \mod 18$$ holds.
Reminder: Euler's totient function is given by $$\phi(n) = n\prod_{p_i|n}\left(1-\frac1{p_i}\right).$$

I actually don't know, how to even approach this. What is the common way, to approach this type of question? How do i start solving this? I tried simplifying to this:

\begin{align} x^{98} &\equiv 7 \mod 2 \Rightarrow x^{98} ≡ 1 \mod 2\\ x^{98} &\equiv 7 \mod 9 \end{align} but i'm not sure if this is the right approach.

Any help would be appreciated.

$\endgroup$
  • $\begingroup$ So, what have you tried, on your own? And your thought process while addressing this problem that has been assigned to you, and (not MSE). $\endgroup$ – Namaste Aug 9 '17 at 2:09
3
$\begingroup$

The idea is to resort to Euler's Theorem. You want to solve the equation $$x^{98}\equiv 7\,(\text{mod } 18).$$ This, in particular, would imply that $x^{98}=7 + 18\cdot n$ for some $n\in\mathbb{N}$, hence $x$ has to be coprime with $18$ (if $p$ divides $x$ and $18$, then it divides $x^{98}$ and $18$ and so $7$ as well, which is impossible). Thus you are in the hypothesis of Euler's Theorem: $x$ and $18$ are coprime and so $$x^{\varphi(18)}\equiv 1\,(\text{mod } 18).$$ By repeatedly using this relation, you should be able to simplify your equation to something more handy.

$\endgroup$
2
$\begingroup$

If $x$ is relatively prime to $18$ then $x^n$ has to be relatively prime to $18$ too. There are only six residues modulo $18$ that do this, the rest are multiples of $2$ or $3$. So $x^0=1, x^1=x, x^2, ...$ cycle among these six residues and you have $x^6\equiv x^0=1$.

Then $x^{98}\equiv x^{92}\equiv x^{86}\equiv ...$ and you get all the way down to $x^2$ where $2$ is the remainder when you divide $98$ by $6$. And solving $x^2\equiv 7 \bmod 18$ will be easy.

$\endgroup$
1
$\begingroup$

The form of Euler's totient function $\phi$ given there is not very practical, and I notice that you didn't give the value for $\phi(18)$. Here's it's easier to use that for $p$ prime, $\phi(p^k) = p^{k-1}(p-1)$ and that $\phi$ is multiplicative between coprime numbers.

So $\phi(18) = \phi(3^2)\phi(2) = 3^1(3-1)(2-1) = 6$.

Thus any number $a$ coprime to $18$ has $a^6\equiv 1 \bmod 18$ (Euler's theorem).

Since $x^{98}\equiv 7$ is coprime to $18$, $x$ is also. Applying $x^6\equiv 1$ we can see that $x^{96}\equiv 1\bmod 18 $ and thus $x^{98}\equiv x^2\bmod 18$. By inspection, since $7+18=25$, we can see that $x\equiv 5$ is an answer to $x^2\equiv 7 \bmod 18$ and thus $x\equiv -5\equiv 13 \bmod 18$ is also an answer.


A couple of notes:

  • Because we ended up looking for $x^2\equiv 7 \bmod 18$, we needed that $7$ is a quadratic residue $\bmod 18$, which is only true of half the values coprime to $18$. If the question had $5$ in place of $7$, there would be no answer.
  • If we were looking at a modulus divisible by two odd primes, or by an odd prime and $4$, there would be more than two answers (for any soluble system). For example $x^2\equiv 13 \bmod 36$ has $x\equiv \{7, 11,25,29\}\bmod 36$.
$\endgroup$
0
$\begingroup$

Thank you for the answers,

I hope I got it right so I solved this question for example:

Find the last digit of $7^{2013}$

so obviously

$7^{2013} ≡ x(mod 10)$

so my thought process was the same, i know that $gcd(7,10)=1$

$φ(10)=φ(5-1)φ(2-1)=4$

then $(7^4)^{503}*7≡x(mod10)$

finally: $$7≡x(mod10)$$

so the final answer is 7, I hope I got it right...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.