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

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$ ?

HINT:

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

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

• Thanks your answer. However in my course we have never seen this function, is there any other way of solving this ? – Shuzheng Sep 21 '13 at 12:34
• @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$ – lab bhattacharjee Sep 21 '13 at 12:36
• Thanks a lot. That answer I understand and know how to apply. – Shuzheng Sep 21 '13 at 12:48
• @NicolasLykkeIversen, my pleasure – lab bhattacharjee Sep 21 '13 at 12:49

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/

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