Всегда ли при нахождении остатка от деления в конце мы будем получать, что делимое будет сравнимо по модулю с a*(+-1)^k?

Да. Но это абсолютно бесполезный ответ.
Чтобы доказать требуемое, вы можете взять к = 1, и положить а=остаток от делимого.
Хотелось бы чтобы такое сравнение выполнялось через маленькое число шагов в преобразованиях. А это своего рода искусство. Скажем, в вашем примере можно было заметить, что 16^2015=32^1612, И решение получилось бы гораздо короче. (Я заметила это, перейдя к основанию 2)