$A^7 \not\equiv A \pmod{13}$ implies $A^{78} + 1 \equiv 0 \pmod{169}$

Question

Let variable $A$ is integer and $A^7 \not\equiv A(\mod 13)$.

Prove that $A^{78} + 1 \equiv 0 \pmod{169}$

Could someone explain, how to solve this type of problems? Any help would be greatly appreciated.

Answer 1

Here is an extended hint - you need to know the Fermat and Euler/Fermat congruences to do this kind of problem.

First work modulo $13$

Little Fermat gives us that $A^{12}-1=(A^6-1)(A^6+1)\equiv 0 \mod 13$

We can't have $A^6-1\equiv 0$ because then $A^7\equiv A$ contrary to the condition, so we must have $A^6+1\equiv 0$.

Now we have $\varphi(169)=156=2\cdot 78$ so that Euler/Fermat gives us that $A^{156}-1=(A^{78}+1)(A^{78}-1) \equiv 0 \mod 169$

The two factors here differ by $2$, so can't both be divisible by $13$. Now use the reformulated condition with the fact that $78=6\cdot 13$ to determine which factor is divisible by $13$ - this factor must be divisible by $169$ to make the $\mod 169$ congruence work.

Answer 2

As Yiyan Lee has identified, $$13\nmid A(A^6-1)\implies13\nmid A\implies(13,A)=1$$

Using Fermat's Little Theorem, $\displaystyle A^{13-1}\equiv1\pmod{13}$

$\displaystyle\iff 13$ divides $A^{12}-1=(A^6-1)(A^6+1)$

Again as $\displaystyle13\nmid (A^6-1),13$ must divide $A^6+1\implies A^6=13a-1$ for some integer $a$

Finally using Binomial Theorem , $\displaystyle A^{78}=(A^6)^{13}=(-1+13a)^{13}=(-1)^{13}+\binom{13}113a(-1)^{12}+O(13a)^2\equiv-1\pmod{13^2}$