• ↓
  • ↑
  • ⇑
 
Записи с темой: теория чисел (список заголовков)
11:23 

Теория чисел. Интересная системка :)

IWannaBeTheVeryBest
"Решить в натуральных числах систему
`x + y = 884`
`[x,y] = 189(x,y) `"
В квадратных скобках НОК, в круглых - НОД.
Ну вообще, решением в натуральных числах первого уравнения будет система
`{(x = n),(y = 884 - n):}`, `n \in {1 \dots 883}`
или
`{(x = 884 - n),(y = n):}`
Второе уравнение домножил на `(x, y)`. Получил
`xy = 189(x, y)^2`
Можно еще преобразовать. Если `(x, y) = d`, то существуют такие целые a и b, что `ax + by = d`. Отсюда
`xy = 189(ax + by)^2`
Вообще, я здесь уперся в идею, что `xy` должно быть кратно `189`.
Из 883 чисел нам подходят те, которые, как минимум, делятся на 7.
Еще что... Ну по-сути задачу можно переписать в виде
"Найти все натуральные `n` из диапазона `1 \dots 883`, такие что `(884 - n)*n` кратно `189`"
Может еще какие идеи есть?

@темы: Теория чисел

23:03 

Простые числа

IWannaBeTheVeryBest
"Найти все простые `p`, такие, что `3p + 20` и `3p + 22` тоже простые"
Ну любое простое число представимо в виде
`p = 6k +- 1`, `k \in Z`
Подставим в наши выражения
`3(6k + 1) + 20 = 18k + 23 = 6 * 3k + 6 * 4 - 1 = 6(3k + 4) - 1 sim 6q - 1`
`3(6k - 1) + 20 = 18k + 17 = 6 * 3k + 6 * 3 - 1 = 6(3k + 3) - 1 sim 6q - 1`
`3(6k + 1) + 22 = 18k + 25 = 6 * 3k + 6 * 4 + 1 sim 6q + 1`
`3(6k - 1) + 22 = 18k + 19 = 6 * 3k + 6 * 3 + 1 sim 6q + 1`
Проблема только в том, что простое число лишь представимо в таком виде. Однако `6k + 1` не всегда является простым. Если `k = 4` то это составное число.
То есть я тут как бы доказал, что если мы подставим в `3p + 20` любое простое число, то мы будем получать числа вида `6k - 1`, не обязательно простые.

@темы: Теория чисел

13:23 

Теория чисел. Системы счисления.

IWannaBeTheVeryBest
"На какую цифру оканчивается число `32^101 + 35^301` в 15-чной системе счисления?"
Вроде знаю как решать. Чисто проверить верно или нет.
Изначально число дано в 10 системе счисления. Для перевода числа из десятичной в любую другую, мы делим данное число на основание системы ну и дальше составляем ответ из одного значения частного, и остальных остатков. По сути задачу можно переопределить так
"Найти остаток от деления `32^101 + 35^301` на 15"
Так как `32 = 15 * 2 + 2`, то можно сделать преобразование
`32^101 -= 2^101`
Дальше по теореме Эйлера
$a^{\phi(n)} \equiv 1 (mod n)$, где `(a, n) = 1`
В таком случае, $2^{\phi(15)} \equiv 2^8 \equiv 1(mod 15)$
Тогда
`2^101 -= 2^96 * 32 -= (2^8)^12 * 32 -= 32` $\equiv 2 (mod 15)$
Второе слагаемое делится на 5, но не делится на 3. Поэтому нам надо найти остаток от деления `35^301/3`. Кстати, можно ли тут искать остаток `7^301/3`?
`35^301 -= 2^301`
Дальше по теореме Эйлера
$2^2 \equiv 1 (mod 3)$
`2^301 -= (2^2)^150 * 2 -= 2` $\equiv 2 (mod 3)$
Сумма остатков = 4. Ответ 4.

@темы: Теория чисел

20:55 

Теория чисел. Отношение сравнимости.

IWannaBeTheVeryBest
Вопрос чисто формальный. Чем отличается отрицательный остаток от положительного? Ну вот у меня задача
`f(x) = 15x^3 - 33x^2 + 7`. Найти остаток от деления `f(86)` на `11`.
Ну решение такое.
Вычисляем для коэффициентов остатки от деления на 11
$15 \equiv 4 (mod 11)$; $33 \equiv 0 (mod 11)$; $7 \equiv -4 (mod 11)$
Ну и еще $86 \equiv -2 (mod 11)$
$f(86) \equiv f(-2) (mod 11) \equiv 4 * (-2)^3 - 0 - 4 \equiv -36 \equiv -3 \equiv 8 (mod 11)$
И ответ получается 8. А почему бы нам не написать, что
$-36 \equiv -3 (mod 11)$ и не сказать, что ответ -3, а не 8? Или большой разницы нет? просто привычка еще с тригонометрии - брать меньший угол, поэтому как-то на автомате хочется взять число, меньшее по модулю :)

@темы: Теория чисел

22:56 

Теория чисел. Функция Эйлера.

IWannaBeTheVeryBest
`\phi(x) = 2`
В учебнике дано решение, но я его не могу понять никак. Просто на первой фразе встал.
"`x` обладает каноническим разложением. `x = p_1^{a_1} * \dots * p_k^{a_k}`. При этом `\phi(x) = p_1^{a_1 - 1} * \dots * p_k^{a_k - 1} * (p_1 - 1) * \dots * (p_k - 1)`
Пусть `\phi(x) = 2^m*l`, где `l` - нечетное. Поскольку для нечетного простого числа `p` величина `p - 1` четна, то в каноническом разложении `x` имеется не более `m` нечетных простых множителей." (дальше попробую сам понять)
Не понимаю причинно следственную связь. Как из одного вытекает другое. Все, что удалось мне выжать
`2^m * l` четное число.
`2^m * l = p_1^{a_1 - 1} * \dots * p_k^{a_k - 1} * (p_1 - 1) * \dots * (p_k - 1)`
Ну и понятно, что в последнем равенстве, справа не все множители нечетные.

@темы: Теория чисел

22:21 

Теория чисел. Остатки

IWannaBeTheVeryBest
"Доказать, что квадрат любого целого числа не представим в виде `4k + 2` где `k \in Z`"
Решал так. Ну предположим, что у нас есть некоторое число `a = 4q + r`. `0 <= r < 4`, `q \in Z`. Тогда `a^2 = (4q + r)^2 = 16q^2 + 8qr + r^2`.
1) `r = 0`
`a^2 = 16q^2 = |k = 4q| = 4k`
2) `r = 1`
`a^2 = 16q^2 + 8q + 1 = 4q(4q + 2) + 1 = |k = q(4q + 2)| = 4k + 1`
3) `r = 2`
`a^2 = 16q^2 + 16q + 4 = 4(4q^2 + 4q + 1) = |k = 4q^2 + 4q + 1| = 4k`
4) `r = 3`
`a^2 = 16q^2 + 24q + 9 = 4q(4q + 6) + 8 + 1 = 4(q(4q + 6) + 2) + 1 = |k = q(4q + 6) + 2| = 4k + 1`
Соответственно, квадрат любого числа представим либо в виде `4k` либо в виде `4k + 1`.
Верно? Если да, то меня стал мучить такой вопрос.
`a^2 \neq 4k + 2 = 2(2k + 1)`
`a \neq +- sqrt(2) * sqrt(2k + 1)`
То есть, по сути, здесь говорится, что так как `a` - целое и оно неравно `+- sqrt(2) * sqrt(2k + 1)`, то вообще говоря последнее не является целым числом.
Вопрос такой. А где-то действительно есть такая теоремка, что произведение нечетного числа на двойку есть число из которого не извлекается квадратный корень? ну или квадратный корень произведения двойки на нечетное число есть число иррациональное? Или это слишком примитивно? :D Просто я сомневаюсь, что я открыл что-то новое.
Однако с ходу не могу придумать этому доказательства.

@темы: Теория чисел

21:40 

"Давай делиться"

wpoms.
Step by step ...


Найдите все натуральные числа `x, y` такие, что `y` делит `(x^2 + 1)` и `x^2` делит `(y^3 + 1)`.



@темы: Теория чисел

11:05 

Найти первообразный корень (mod 2*5^5)

Я посмотрела в интернете, как такое примерно делать. Но не уверена в правильности моего решения.
Итак, сначала ищу первообразный корень по модулю 5^5:
1) 2 - первообразный корень по модулю 5
2) тогда число вида (2+5t)^4 не должно быть сравнимо с 1 по модулю 25. При t=0, 2^4 не сравнимо с 1 по модулю 25
3) значит, 2 - первообразный корень по mod5^s, где s>=2 (Не уверена...можно ли так обобщать для всех случаев s>=2??)
4) пользуясь теоремой, получаю, что 2+5^5 - нечетное число. Значит, оно является первообразным корнем (mod 2*5^5).

@темы: Теория чисел

10:27 

Обратный элемент в поле вычетов

Добрый день!
Подскажите, пожалуйста, почему в поле `Z_p` обратный элемент имеет вид `a^(-1) = a^(p-2)`. Насколько я понимаю, используется МТФ, но вывести данную формулу не могу. Спасибо

@темы: Высшая алгебра, Теория чисел

21:11 

Целое и делит

wpoms.
Step by step ...


Пусть `x` - вещественное число такое, что `t = x + x^{-1}` - целое, большее `2`, число. Докажите, что `t_n = x^n + x^{-n}` является целым числом для всех положительных целых чисел `n`. Определите значения `n`, для которых `t` делит `t_n`.



@темы: Теория чисел

21:42 

Кратно и квадратно

wpoms.
Step by step ...


Положительные целые числа `p`, `a` и `b` удовлетворяют уравнению `p^2 + a^2 = b^2`. Докажите, что если `p` является простым и `p > 3`, то `a` кратно` 12` и `2*(p + a + 1)` является полным квадратом.



@темы: Теория чисел

01:18 

Непредставительные числа

wpoms.
Step by step ...


Число `1000` может быть записано как сумма `16` последовательных натуральных чисел: `1000 = 55 + 56 + ... + 70`. Найдите все натуральные числа, которые не могут быть записаны как сумма двух или более последовательных натуральных чисел.



@темы: Теория чисел

22:54 

Целая часть числа

wpoms.
Step by step ...


Обозначим для всех действительных чисел `x` наибольшее целое число, меньшее или равное `x` как `lfloor x rfloor`. Пусть `alpha = 2 + sqrt(3)`. Докажите, что `alpha^n - lfloor alpha^n rfloor = 1 - alpha^{-n}`, для `n = 0,1, 2, .. .`



@темы: Теория чисел

17:05 

Произведение простых чисел

wpoms.
Step by step ...


Предположим, что `n` равно произведению различных простых чисел `a`, `b`, `c`, `d` таких, что:
(a) `a + c = d`;
(b) `a*(a + b + c + d) = c*(d - b)`;
(c) `1 + b*c + d = b*d`.
Найдите `n`.



@темы: Теория чисел

10:17 

wpoms.
Step by step ...


Таблица размером `3 times n` заполняется следующим образом: в первой строке записаны числа от `1` до `n`, упорядоченные по возрастанию слева направо. Вторая строка получена из первой циклическим сдвигом, то есть в этом ряду записаны числа `i, i + 1, . . . , n - 1, n, 1, 2, . . . , i - 1` для некоторого `i`. В третьей строке записаны в некотором порядке числа от `1` до `n`, при этом сумма чисел в каждой из `n` колонок одна и та же.
Для каких значений `n` возможно заполнение таблицы по указанным выше правилам? Для тех `n`, для которых это возможно сделать, определите количество различных способов заполнить таблицу.



@темы: Теория чисел

18:07 

Натуральные числа. Прошу любить и жаловать

wpoms.
Step by step ...


Последовательность `a_1, a_2, a_3, a_4,...` определяется соотношениями `a_1 = 1`, `a_2 = 1`, `a_3 = 1` и `a_{n+1}*a_{n-2} - a_{n}*a_{n-1} = 2`, для всех `n >= 3`. Докажите, что `a_n` является натуральным числом для всех `n >= 1`.



@темы: Теория чисел

22:36 

Тройки

wpoms.
Step by step ...


Найдите все тройки натуральных чисел `(p, q, n)` (`p` и `q` простые), удовлетворяющие равенству
`p*(p + 3) + q*(q + 3) = n*(n + 3)`.




@темы: Теория чисел

21:58 

НОК

wpoms.
Step by step ...


Giraldo написал пять различных натуральных чисел в вершинах пятиугольника. Затем он написал на каждой стороне наименьшее общее кратное чисел, которые записаны в концах этих сторон, после чего он заметил, что все пять чисел, написанных на сторонах равны. Какое наименьшее число могло быть написано на стороне пятиугольника?



@темы: Теория чисел

20:28 

Делимость числа

Добрый вечер!

Есть задача: доказать, что произведение трёх последовательных натуральных чисел, среднее из которых является кубом натурального числа, делится на `504`.

Идей как-то совсем нет, разве что само условие переписал как: `(b^3-1)*b^3*(b^3+1)`. Ну и `504` это`2*2*2*3*3*7`.
Но вот что делать дальше? Использовать какие-нибудь теоремы о НОД? Или может у кубов есть какие-то особенные свойства делимости?

Помогите, пожалуйста.

@темы: Теория чисел

08:35 

Число в степени

wpoms.
Step by step ...


Покажите, что существует положительное целое `N` такое, что десятичное представление числа `2000^N` начинается с `200120012001`.



@темы: Теория чисел

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная