If the product of the factors of $30^{12}$ that are congruent to 1 mod 7 can be expressed as $2^{a} \cdot 3^{b} \cdot 5^{c},$ find $a+b+c$.
I tried using mod rules to simplify but I got a very strange answer which was divisible by 7 and did not fit the answer criteria. I noted that 15 is 1 mod 7 and even 8 is 1 mod 7, but I do not know how to go ahead from there.
EDIT: I also noted that 6 is -1 mod 7 and 30^12 is 1 mod 7. But that didn't help either.
Best Answer
Since $30=2\cdot 3\cdot 5$, the factors of $30^{12}$ are of the form $2^x\cdot3^y\cdot5^z$ where $x,y,z$ are between $0$ and $12$.
Since $7$ is prime, we know from Fermat's little theorem that $a^6 \equiv 1 \bmod 7$ for $a$ coprime to $7$. So, if we have $2^x\cdot3^y\cdot5^z\equiv 1 \bmod 7 $ for some particular $x,y,z$ we can also say that $2^{x+6}\cdot3^y\cdot5^z\equiv1 \bmod 7 $ and similarly $2^x\cdot3^{y+6}\cdot5^z$, $2^x\cdot3^y\cdot5^{z+6}$ etc.
Directly calculating powers of $2\bmod 7$ we find the cycle is actually only length $3$: $2^0\equiv 1,2^1\equiv 2,2^2\equiv 4,2^3\equiv 8\equiv 1$. So we can focus on $x\in\{0,1,2\}$ and infer other solutions by adding multiples of $3$ to the base $x$ value.
We can also check that powers of both $3$ and $5$ cycle through all $6$ coprime residue values in sequence; $3^y\equiv \{1,3,2,6,4,5,1,\ldots\}$ and $5^z\equiv \{1,5,4,6,2,3,1,\ldots\}$ (starting from zero in both cases).
For $x=0$, which also holds for $x = 3,6,9,12$ giving $2^x\equiv 1 \bmod 7$, we can have $(y,z) = (0,0), (0,6), (0,12), (6,0), (6,6), (6,12), (12,0),(12,6), (12,12)$ and also $(y,z) = (1,1), (2,2), (3,3), (4,4), (5,5)$ and the values formed by adding $6$ to either $y$ or $z$ or both. This gives $9+4\cdot 5 = \fbox{29}$ options for each of the $\fbox{5}$ eligible values of $x$ with the sum of $(y+z)$ over all these options at $108+30+2\cdot 60+90 = \fbox{348}$ and total value of all eligible $x$ at $0+3+6+9+12=\fbox{30}$.
For $x\in \{1,4,7,10\}$, $\fbox{4}$ values totalling $\fbox{22}$ with $2^x\equiv 2\bmod 7$, we can have $(y,z)$ formed from $(\{0,6,12\},\{2,8\})$, $(\{4,10\},\{0,6,12\})$, and also $(1,3), (2,4), (3,5), (5,1)$ with the $+6$ options for $y$ and $z$. Overall $6\cdot 2 + 4\cdot 4 = \fbox{28}$ options for a total $(y+z)$ of $66+78+24+2\cdot 48+72 = \fbox{336}$ per $x$ value.
For $x\in \{2,5,8,11\}$, $\fbox{4}$ values totalling $\fbox{26}$ with $2^x\equiv 4\bmod 7$, we can have $(y,z)$ formed from $(\{0,6,12\},\{4,10\})$, $(\{2,8\},\{0,6,12\})$, and also $(1,5), (3,1), (4,2), (5,3)$ with the $+6$ options for $y$ and $z$. This also gives $\fbox{28}$ options per $x$ value for a total $(y+z)$ of $\fbox{336}$.
Across all options then we have $5\cdot 348 + 4\cdot 336 + 4\cdot 336 = 4428$ total for $(y+z)$ and $29\cdot 30 + 28\cdot 22+ 28\cdot 26 = 2214$ total for $x$.
This gives use the desired $(a+b+c)$ total of $2214+4428 = 6642$.