Теория чисел
Докажите, что при целом
q >= 2 каждое натуральное число n может быть единственым образом представлено в виде n = ak*q^k + a(k-1)
*q^(k-1) + ... + a1*q + a0, где
0 <= ak, ak-1,...,a1, a0 < q
Доказательство от обратного что число может быть единственным образом представлено в виде (1), где для любое Ai строго меньше q и нестрого больше 0 (0 <= Ai < q) , а q >= 2.
Допустим что есть разные наборы чисел Аi и Bi такие что дают одинаковое число n, причем для любого индекса i соблюдается условия Bi != Ai и Bi > Ai (2).
То есть такое число m > 0 (3) т.к. любое Сi > 0.
Число m можно представить в виде разности сумм (4) чисел Bi и Ai, но из этого следует m = n - n = 0 что противоречит условию m > 0.
Следовательно для для любого индекса i должно соблюдаться условие Bi = Ai, что и требовалось доказать.
раскрыть ветку (4)
причем для любого индекса i соблюдается условия Bi != Ai и Bi > Ai (2).
Так ты доказал только для таких наборов, что ими нельзя представить одно и то же число. А это слишком сильное ограничение, наборы могут отличаться не для каждого i, и для разных i может выполняться как Bi > Ai, так и Bi < Ai.
раскрыть ветку (2)
Это тоже можно обойти, выбрав максимальный такой индекс, в котором представления различаются. Но тогда нужно знать свойства сравнения натуральных чисел и их связи с умножением и делением. Задача настолько базовая, что главное не использовать лишний раз какой-то факт, который обычно доказывается после. Свойства, насколько я помню, выводятся для теории Пеано и представления в той или иной системе счисления не требуют.
Вообще не совсем точное доказательство, из условия (2) можно убрать Bi > Ai. тогда все равно будет получаться число m не равное 0. Это условие также не будет согласовываться с последним уравнением (4).
Лига математиков
1.2K постов2.6K подписчик