가짜 소수(13319, P5, c++)

가짜 소수

가짜 소수

문제

문제에 수식이 들어있어서 사진으로 대체한다.

페르마의 소정리는 소수 p에 대해 a^(p-1) ≡ 1 (mod p)이다.
하지만 페르마의 소정리를 만족한다고 소수가 되는 것은 아니다.

지구이는 a를 2~500까지 확인해 페르마의 소정리를 만족한다면 소수라고 판별했다.
하지만 논리의 역은 참이 아니고, 반례가 있으니, 그것을 찾으면 되는 문제이다.

풀이

저는 이 문제를 해봤어요..!
예전에 어디지? 암호학 CTF에서 거의 똑같은 문제를 본 적이 있다.
그때는 당연하게도 못 풀었고, 롸업을 본 다음 저런 수가 있구나를 알게 되었다.

다음에 나오면 맞춰야지 생각했는데 백준에서 이 문제를 보게 될 줄을 몰랐다.
저런 페르마의 소정리의 역을 통과하는 수들을 카마이클 수라고 부른다.
수학적 증명은 암호학 공부할 때 정수론 이야기를 쓰면서 해보면 되지 않을까..

Carmichael_number
링크를 가서 보면 (6k+1),(12k+1),(18k+1)이 모두 소수면 곱한 값이 카마이클 수다.
그 중 6K+1이 500보다 커야 하고, 3개 모두 소수를 만드는 k는 100이다.
그렇게 출력을 해줘서 맞았다.

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b, c, d;
    long long n, m, t;
    int total=0;
    
    cout << 601*1201*1801 << ' ' << 601;


    return 0;
}