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.
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$.
You might try a smaller exponent to start with, say $30^{2}$ or $30^{3}$.
Making out a multiplication table would be a good first step. This also makes a lot more sense after plotting out some of the paths toward 1, for example:
$$ \begin{align} 2 * 2 * 2 = 1\\ 2 * 3 * 2 * 3 = 1 \\ 2 * 5 * 5 = 1 \\ \end{align} $$
I prefer using $-2$ instead of $5$. Thus we have instead that $2 * -2 * -2 = 1$. If you get a $-1$, you'll have to make another $-1$ to make $1$.
I've got a method I like.
Start by laying out a 13x13 two dimensional grid. Label your x axis 2 and y axis 3. Ticks on the axes correspond to the exponent for that base. The point (3,0) then would correspond to $2^3*3^0$ which is a solution. Everything on this grid has no factors of 5. Starting with a 2d grid and adding layers works better for counting up points than just starting with a 3d grid.
For each solution point (a,b) there is a corresponding solution point at (a+3, b). If I remove a factor of two, I can add two factors of three to replace it. That is, if (a,b) is a solution point, then (a-1, b+2) is a solution point.
This all makes a very regular repeating pattern. The amount to add to the sum for any point (a, b, c) is simply a+b+c. The sum for the $5^0$ level is 382.
When we go up to the $5^1$ level, that multiplies in a 5 mod 7, and we need an additional 3 mod 7 factor to bring the solution point back into true. So on the $5^1$ level, each solution point is shifted y-wise by one. For every point, we gain two in the exponent (one for the 3 and one for the 5), for 26 of the 31 points, adding $26*2$ to the total, and removing the sum for the points entirely that shift off: $12+15+18+21+24$
Continue this way. If you're careful, you can reuse many of your sums, and it isn't too tedious. Make sure you get all 13 levels (0-12)
Update: It's interesting to see that $a=b$, and the number of cases are the same when there are $2$ or $3$ solutions for $z$, respectively. I have a way to show it is true but right now it's not simple enough to replace the solution below.
I'll adopt Joffan's notation and compute $a$, $b$ and $c$ separately.
First notice that $3^y$ and $5^z$ both cycle through $\{1, 2, 3, 4, 5, 6\} \pmod 7$. So if $x$ and $y$ are fixed then $5^z \equiv 2^{-x} 3^{-y} \pmod 7$ will have $3$ solutions from $1$ to $12$ if $2^x 3^y \equiv 1 \pmod 7$, and $2$ solutions otherwise.
For a given $x$, there are always at least $13 \cdot 2=26$ cases when $y$ cycle through $0$ to $12$. But there is one more solution if and only if $5^z\equiv 2^{-x} 3^{-y} \equiv 1$. Our goal is to find those cases and add to the "base cases".
Next we compute $a$. If $2^x 3^y \equiv 1$ there are two cases:
Case 1: $2^x \equiv 3^y \equiv 1$. There are $3$ cases when $3^y\equiv 1$ for each $x \in \{0,3,6,9,12\}$ so the sum of all these $x$'s is $3 \cdot (3+6+9+12)=3 \cdot 30=90$.
Case 2: $2^x \not \equiv 1$. There are $2$ cases when $3^y \equiv 2^{-x}$ for each $x\in\{1,2,4,5,7,8,10,11\}$ and the sum of all these $x$'s is $2\cdot(78-30)=96$.
Since the sum of $x$'s in the "base" cases is $78\cdot 26=2028$, we have $$a=2028+90+96=2214$$
Finally we compute $b$ and by symmetry $c=b$.
If $3^y 2^x \equiv 1$ we have the following cases (note that if $3^y \not\equiv 1,2,4$ then we can't have $3^y 2^x \equiv 1$):
Case 3: $3^y\equiv 2^x \equiv 1$. There are $5$ cases when $2^x\equiv 1$ for each $y\in\{0,6,12\}$ so the sum of all these $y$'s is $5\cdot(0+6+12)=90$;
Case 4: $3^y \equiv 2, 4$. There are $4$ cases when $2^x\equiv 3^{-y}$ for each $y \in \{2,4,8,10\}$ so the sum of all these $y$'s is $4\cdot (2+4+8+10)=96$;
Therefore $b=c=2028+90+96=2214, a+b+c=3\cdot 2214=6642$.
With Toby Mak's great insight I give a short answer with the least amount of calculation below.
Claim: $a+b+c = (2\cdot 13^2 + 2\cdot 13+5)\cdot 18 = 6642$.
Proof: Suppose the number of $3^{12}$'s divisors congruent to $1 \pmod 7$ is $k$. First we note $2^6 \cdot 3^6 \cdot 5^6$ is one of them, with the sum of exponents equal to $18$. For any other such divisor of the form $2^x 3^y 5^z$, we have $2^{12-x} 3^{12-y} 5^{12-z} \equiv 1 \pmod 7$, therefore we have $(k-1)/2$ pairs of divisors such that the exponents sum to $36$, plus a lonesome divisor $2^6 \cdot 3^6 \cdot 5^6$, henceforth $a+b+c=36(k-1)/2 + 18 = 18k$. (We also know $\color{blue}{a=b=c=6k}$.)
Next, for each of the $13\cdot 13$ pairs of $x,y, 0\le x,y \le 12 $, there are $2$ solutions of $z, 0\le z \le 12$ such that $5^z \equiv 2^{-x} 3^{-y} \pmod 7$, except when $2^x 3^y \equiv 1 \pmod 7$ there are $3$ solutions.
Finally, for each of the $13x$'s$, 0\le x \le 12$ there are $2$ solutions of $y$ such that $3^y \equiv 2^{-x} \pmod 7$, except when $x=0,3,6,12,15$ there are $3$ solutions. Therefore, $k=2\cdot 13^2 + 2 \cdot 13 + 5$ and we are done.
