1
$\begingroup$

I have the following problem:

Problem: What is the remainder of $a^{72} \mod 35$ if $a$ is a whole number not having $5$ or $7$ as divisors.

If $a$ cannot be divided by $5$ or $7$ it cannot be divided by $35$, so the remainder is not $0$.

However the remainder can be everything between $1$ and $34$ excluding numbers divisible by $5$ or $7$ ?

Thanks for your time.

$\endgroup$
1
$\begingroup$

HINT:

Using Carmichael function, $\lambda(35)=12$

If $(a,7)=(a,5)=1\implies (a,35)=1\implies a^{12}\equiv1\pmod{35}$

$\endgroup$
  • $\begingroup$ Thanks your answer. However in my course we have never seen this function, is there any other way of solving this ? $\endgroup$ – Shuzheng Sep 21 '13 at 12:34
  • $\begingroup$ @NicolasLykkeIversen, Have you heard Fermat's little theorem(en.wikipedia.org/wiki/Fermat%27s_little_theorem)? Then $a^{5-1}\equiv1\pmod 5$ and $a^{7-1}\equiv1\pmod 7\implies a^{12}\equiv1\pmod5,$ and $a^{12}\equiv1\pmod7 \implies a^{12}-1$ is divisible by lcm$(5,7)=35$ $\endgroup$ – lab bhattacharjee Sep 21 '13 at 12:36
  • $\begingroup$ Thanks a lot. That answer I understand and know how to apply. $\endgroup$ – Shuzheng Sep 21 '13 at 12:48
  • $\begingroup$ @NicolasLykkeIversen, my pleasure $\endgroup$ – lab bhattacharjee Sep 21 '13 at 12:49
2
$\begingroup$

Since $a$ and $35$ are coprime $(gcd (a, 35) = 1)$, use Euler's totient function: $$a^{\phi(n)} = 1 \hspace{2 pt} mod \hspace{2 pt}n$$

So you get $$a^{\phi(35)} = a^{24} = 1 \hspace{2 pt} mod \hspace{2 pt}35$$

Thus,

$$a^{24^3} = a^{72} = 1^3 mod 35 = 1$$

So $1$ is your remainder.

Example: Set $a = 24$. http://www.calculatorpro.com/calculator/modulo-calculator/

$\endgroup$
  • $\begingroup$ $24^3$ is not $72$; $24\cdot 3$ is. $\endgroup$ – Henning Makholm Sep 28 '13 at 11:14

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.