1

Я хочу сделать подсчет с учетом малой теоремы ферма. У меня есть два любых числа, которые я могу указать.

Например возьмем 60 и 101

Теперь зная эти числа, в теории вы можете передать единицу, манипулируя этими числами.

По сколько я знаю ответ, я скажу что получиться.

Вам понадобиться 32 раза умножить на 60, у вас получиться число 1920 затем вы 19 раз умножить число 101 будет 1919.

1920 - 1919 = 1

Это доказывает, что зная два любых числа, вы можете передать человеку самую малую сумму.

Теперь я пытаюсь этот алгоритм реализовать на С++ но не знаю с чего начать.

Я хочу указывать любые числа и получать цифры на сколько нужно умножить число что бы получить единицу, или возможно я захочу получить число 10. Уверен что это делается в одно строчку, а может и нет.

10
  • Это не оно? e-maxx.ru/algo/export_extended_euclid_algorithm
    – Harry
    7 янв 2020 в 16:30
  • зная два любых числа - не любых, а взаимно простых
    – MBo
    7 янв 2020 в 16:31
  • что значит взаимно простых, я бы хотел брать два любых числа.
    – pinki
    7 янв 2020 в 16:34
  • Это расширенный алгоритм Евклида как правильно указали. Подходит для любых двух взаимно простых чисел. Если вас интересует решение диофантова уравнения ax+by=1, то оно не всегда имеет решение. Можно посмотреть на вики.
    – becouse
    7 янв 2020 в 16:35
  • 1
    Как только для 8 и 16 вы покажете, как получить 1 - так сразу!
    – Harry
    7 янв 2020 в 16:35

1 ответ 1

6

Немножко математики...

Пусть есть числа a и b и у них НОД - d. Тогда

a = kd
b = ld

И любое выражение

ma+nb = (km+ln)d 

будет кратно d. Так что любое значение вы получите только для взаимно простых чисел... А для не взаимнопростых - кратное их НОД.

Использовав для этого расширенный алгоритм Евклида.

Привожу его реализацию

int gcd (int a, int b, int & x, int & y)
{
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
4
  • Такое чувство что меня развели, я думал из любого числа можно получить 1 А не только из простых.
    – pinki
    7 янв 2020 в 16:43
  • Из любых взаимно простых. Например, из 12 и 25. Оба - составные, но 25-2*12=1. Простые и взаимно простые - это разные вещи.
    – Harry
    7 янв 2020 в 16:44
  • Спасибо теперь вроде начинаю понимать.
    – pinki
    7 янв 2020 в 16:46
  • Всегда пожалуйста :)
    – Harry
    7 янв 2020 в 16:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.