More fun in 2015, Part 17

Here is a rather abstract group-theoretical SOLUTION I: The multiplicative group $\mathbb{Z_{2015}^*}$ is isomorphic to $\mathbb{Z_{5}^*}\times\mathbb{Z_{13}^*}\times\mathbb{Z_{31}^*}$ , by the Chinese Remainder Theorem, which in turn is isomorphic to the additive group $\mathbb{Z_{4}}\times\mathbb{Z_{12}}\times\mathbb{Z_{30}}$ . We seek the solutions of $30(a,b,c)\equiv(0,0,0).$ This congruency holds if $a$ and $b$ are even, so that there are $2\times6\times30=\boxed{360}$ solutions.

Here is an elementary SOLUTION II that does not use any theory beyond Fermat's Little Theorem and the Chinese Remainder Theorem. As Isaac observed, the congruency $a^{30}\equiv1\pmod{2015}$ holds if and only if the same congruency holds modulo the prime factors of $2015$ , namely, $5, 13$ and $31$ . In fact, by the Chinese Remainder Theorem, the number of solutions modulo 2015 is the product of the numbers of solutions modulo $5, 13$ and $31$ .

Now $a^{30}\equiv1\pmod{31}$ has $30$ solutions, by Fermat's Little Theorem.

$a^{30}\equiv1\pmod{5}$ is equivalent to $a^{2}\equiv1\pmod{5}$ , by Fermat, and that congruency has 2 solutions, $1$ and $4$ , by inspection.

$a^{30}\equiv1\pmod{13}$ is equivalent to $a^{6}\equiv1\pmod{13}$ , by Fermat, and that congruency has 6 solutions, $1,3,4,9,10,12$ by inspection (we get the last three by symmetry).

Thus our answer is, once again, $2\times6\times30=\boxed{360}$

SOLUTION III: We can use the following result, which we leave as an exercise to the reader: If $p$ is a prime and $n$ is a positive integer , then the congruency $a^n\equiv{1} \pmod{p}$ has $\gcd(p-1,n)$ solutions. This gives us the number of solutions of $a^{30}\equiv{1}$ modulo 5, 13, and 31 right away.

I'm just going to give a sketch of my proof since i feel it is not the most optimal way to solve this type of problem.

First we note that $2015=5\times13\times31$ .

If $a^{ 30 }\equiv1 \pmod {2015}$ Then it must also satisfy the three equations:

$\begin{cases} a^{ 30 }\equiv1 \pmod {5}\\ a^{ 30 }\equiv1 \pmod {13}\\ a^{ 30 }\equiv1 \pmod {31} \end{cases}$

From Fermat's little theorem we know $n^{ 4 }\equiv1 \pmod {5}$ for $n\neq 5k$ .

Raising both sides to the power of $15$ we get $n^{ 60}\equiv1 \pmod {5}$ for $n\neq 5k$ .

Using the same argument we can get $n^{ 60 }\equiv1^ \pmod {13}$ for $n\neq 13k$ .

This implies that $n^{ 60 }\equiv1^ \pmod {65}$ for $n\neq 5k$ and $n\neq 13k$ .

Therefore $a^{ 30 }\equiv1 \pmod {65}$ is satisfied when $n^{ 2}\equiv{a} \pmod {65}$ for $n\neq 5k$ and $n\neq 13k$ .

We then consider the Quadratic Residues $\pmod {65}$ discounting all the ones which are multiples of $5$ and $13$ . After some hard calculation we are left with a set of $12$ values of $a$ between $0$ and $65$ , $a={1,4,9,14,16,29,36,49,51,56,61,64}$

We know that $a$ must satisfy $a=a_i+65m$ where $a_i$ denotes a number in the set above and $0\le m \le 30$ since $1\leq{a}\leq2015$ . The number of $a$ that satisfy this is $31\times 12=372$ . This only satisfies the first two equations though.

So now lets consider $a^{ 30 }\equiv1 \pmod {31}$ . Using Fermat's little theorem again we can see this holds for all $a$ such that $a\neq 31k$ . All we need to do now is to find out how many multiples of $31$ are in $a=a_i+65m$ for $0\le m \le 30$ and subtract them from $372$ .

You can see there is only $1$ value of $m$ per $a_i$ .

Therefore the answer is $372-12=\boxed{360}$

Please note this is my first proof and i've only recently been doing these types of problems. If i've made any mistakes please say. I have a feeling there is a five line solution i am unaware of. I can't tell if i've been creative or stupid.

Otto sir's solution is very good.

But just for sake of variety, lemme post a CS solution(in python language).

1
2
3
4
5
6
7
8
9

li = []
for i in range(1,2016):
    a = i**30
    b = 1
    c = a-b
    if c%2015==0:
        li.append(c)

print(len(li))

It prints 360.

I solved this using NT, but since there are many NT solutions, I'll post a one-line CS solution.

1

print(len([a for a in range(1, 2016) if (a**30 - 1) % 2015 == 0]))

Which correctly outputs the answer of $\boxed{360}$