7 and 500, Modulo Challenge

By Carmichael function , there exist a positive integer $n$ such that $7^{\lambda (n)} \equiv 1 \pmod {n}$ for $\text{gcd}(7,n) = 1$

Because $500 = 2^2 \times 5^3$ ,

$\begin{aligned} \lambda (500) & = & \text{lcm} \left ( \lambda (2^2) , \lambda (5^3) \right ) \\ & = & \text{lcm} \left ( \phi (2^2), \phi(5^3) \right ) \\ & = & \text{lcm} \left ( 2, 100 \right ) \\ & = & 100 \\ \end{aligned}$

So $7^{100} \equiv 1 \pmod{500}$ or $7^{100} - 1 \equiv 0 \pmod{500}$ ,

Note that the last digit of $7^x$ are $7,9,3,1,7,9,3,1, \ldots$ with period $4$ , knowing that the last digit of $\left ( 7^x -1 \right )$ is $0$ then $x$ must be a multiple of $4$

Consider modulo $500$ , for a certain positive integer $m$ , $7^{4m} - 1 \equiv (7^4)^m - 1 \equiv (-99)^m - 1 \equiv (-1)^m (100 - 1)^m - 1$

Trial and error shows that the smallest $m$ is $5$ , hence $x = 4m = \boxed{20}$

$7^x\equiv1\text{ (mod 500)} \Rightarrow 7^x-1=500k$ for $k$ is a positive integer.

Consider the pattern of the last digit of $7^x$ :

$7^1\rightarrow7$

$7^2\rightarrow9$

$7^3\rightarrow3$

$7^4\rightarrow1$

The last digit of $\text{RHS}$ , $500k$ is $0$ .

The last digit of $\text{LHS}$ , $7^x-1$ is also $0$ if and only if $x$ is divisible by $4$ .

Let $x=4m$ , and substitute into the previous expression,

$7^{4m}-1=500k$

$(7^m-1)(7^m+1)(7^{2m}+1)=2^2\times5^3\times k$

$\text{LHS}$ is divisible by $2^2\times5^3$

For $2^2$ , $7^m-1$ and $7^m+1$ are both even numbers so their product is divisible by $4$ .

For $5^3$ , the power of $7$ must be in the form of $4n+2$ for the last digit of $(7^m+1)$ or $(7^{2m}+1)$ be $0$ that can be divisible by $5$ . Furthermore, to get a smaller $m$ , we choose to let $7^{2m}+1$ divisible by 5.

$7^{2m}+1$

$=49^m+1$

$=(50-1)^m+1$

$={m \choose 0}(-1)^050^m+{m \choose 1}(-1)^150^{m-1}+{m \choose 2}(-1)^250^{m-2}+...+{m \choose m-1}(-1)^{m-1}(50)^1$

Every terms except the last can be divisible by $5^3=125$ .The last term, which is ${m \choose m-1}(-1)^{m-1}(50)^1$ , can be divisible by $125$ if only $m \choose m-1$ can be divisible by $5$ , then the smallest possible value of $m$ will be $5$ . Now, the whole expression is divisible by $5^3=125$ .

Substitute $m=5$ ,

$x=4m=20$

7^x=500k+1 units digit of 7^x has to end with 1. Hence x is a multiple of 4. 7^4n=500k+1 (2401)^n=500k+1 2401^2 ends with 801 2401^4 will end with 1201(pattern)..and 2401^20 will end with 2001 Thats how we do questions like a boss.