Proth's theorem
ಸಂಖ್ಯಾ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಪ್ರೋಥ್ ಪ್ರಮೇಯವು ಪ್ರೋಥ್ ಸಂಖ್ಯೆಗಳಿಗೆ ಪ್ರಾಥಮಿಕ ಪರೀಕ್ಷೆಯಾಗಿದೆ. ಇದು p ಒಂದು ಆದ್ಯಸಂಖ್ಯೆಯಾಗಿದ್ದರೆ, k2n + 1 ರೂಪದಲ್ಲಿ k ಬೆಸ ಮತ್ತು k <2n ಆಗಿದ್ದರೆ, ಮತ್ತು a ಎಂಬ ಪೂರ್ಣಾಂಕವಿದ್ದರೆ, ಅದಕ್ಕೆ p ಅವಿಭಾಜ್ಯವಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ p ಅನ್ನು ಪ್ರೋಥ್ ಪ್ರೈಮ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇದು ಪ್ರಾಯೋಗಿಕ ಪರೀಕ್ಷೆಯಾಗಿದೆ ಏಕೆಂದರೆ p ಅವಿಭಾಜ್ಯವಾಗಿದ್ದರೆ, ಯಾವುದೇ ಆಯ್ಕೆ ಮಾಡಿದ a ಕೆಲಸ ಮಾಡುವ ಸುಮಾರು 50 ಪ್ರತಿಶತದಷ್ಟು ಅವಕಾಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಇದಲ್ಲದೆ, ಲೆಕ್ಕಾಚಾರವು ಮಾಡ್ p ಆಗಿರುವುದರಿಂದ, p ಗಿಂತ ಚಿಕ್ಕದಾದ ಮೌಲ್ಯಗಳನ್ನು ಮಾತ್ರ ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಬೇಕಾಗುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಆಚರಣೆಯಲ್ಲಿ, p ಯ ಕ್ವಾಡ್ರಾಟಿಕ್ ನಾನ್ ರೆಸಿಡ್ಯೂ ಅನ್ನು ಮಾರ್ಪಡಿಸಿದ ಯೂಕ್ಲಿಡ್ನ ಅಲ್ಗಾರಿದಮ್ನ ಮೂಲಕ ಕಂಡುಹಿಡಿಯಲಾಗುತ್ತದೆ ಮತ್ತು a ಯ ಮೌಲ್ಯವಾಗಿ ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ, ಏಕೆಂದರೆ a ಕ್ವಾಡ್ರಾಟಿಕ್ ನಾನ್ ರೆಸಿಡ್ಯೂ ಮಾಡ್ಯುಲೋ p ಆಗಿದ್ದರೆ, ವ್ಯತಿರಿಕ್ತವೂ ಸಹ ನಿಜವಾಗಿದೆ, ಮತ್ತು ಪರೀಕ್ಷೆಯು ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಆದ್ದರಿಂದ, ಅನೇಕ ಮಾಂಟೆ ಕಾರ್ಲೊ ಪ್ರಾಥಮಿಕತೆ ಪರೀಕ್ಷೆಗಳಿಗೆ (ತಪ್ಪು ಧನಾತ್ಮಕತೆಯನ್ನು ಹಿಂದಿರುಗಿಸಬಲ್ಲ ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳು) ವ್ಯತಿರಿಕ್ತವಾಗಿ, ಪ್ರೋತ್ಸ್ ಪ್ರಮೇಯವನ್ನು ಆಧರಿಸಿದ ಪ್ರಾಥಮಿಕತೆ ಪರೀಕ್ಷಾ ಕ್ರಮಾವಳಿಯು ಲಾಸ್ ವೇಗಾಸ್ ಕ್ರಮಾವಳಿಯಾಗಿದ್ದು, ಯಾವಾಗಲೂ ಸರಿಯಾದ ಉತ್ತರವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ ಆದರೆ ಯಾದೃಚ್ಛಿಕವಾಗಿ ಬದಲಾಗುವ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದೊಂದಿಗೆ. ಮೇಲೆ ವಿವರಿಸಿದಂತೆ a ಅನ್ನು ಕ್ವಾಡ್ರಾಟಿಕ್ ನಾನ್ ರೆಸಿಡ್ಯೂ ಎಂದು ಆಯ್ಕೆ ಮಾಡಿದರೆ, ರನ್ಟೈಮ್ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ, ಅಂತಹ ಕ್ವಾಡ್ರಾಟಿಕ್ ನಾನ್ ರೆಸಿಡ್ಯೂವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕಳೆದ ಸಮಯಕ್ಕೆ ಸುರಕ್ಷಿತವಾಗಿರುತ್ತದೆ. ನಿಜವಾದ ಪರೀಕ್ಷೆಗೆ ಹೋಲಿಸಿದರೆ ಅಂತಹ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ತುಂಬಾ ವೇಗವಾಗಿರುತ್ತದೆ. ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಉದಾಹರಣೆಗಳು ಪ್ರಮೇಯದ ಉದಾಹರಣೆಗಳಲ್ಲಿ ಇವು ಸೇರಿವೆಃ p = 3 = 1 (21) + 1, ನಾವು 2 (3-1)/2 + 1 = 3 ಅನ್ನು 3 ರಿಂದ ಭಾಗಿಸಬಹುದು, ಆದ್ದರಿಂದ 3 ಅವಿಭಾಜ್ಯವಾಗಿದೆ. p = 5 = 1 (22) + 1 ಗೆ, 3 (5-1)/2 + 1 = 10 ಅನ್ನು 5 ರಿಂದ ಭಾಗಿಸಬಹುದು, ಆದ್ದರಿಂದ 5 ಅವಿಭಾಜ್ಯವಾಗಿದೆ. p = 13 = 3 (22) + 1 ಗೆ, ನಾವು 5 (13-1)/2 + 1 = 15626 ಅನ್ನು 13 ರಿಂದ ಭಾಗಿಸಬಹುದು, ಆದ್ದರಿಂದ 13 ಅವಿಭಾಜ್ಯವಾಗಿದೆ. ಅವಿಭಾಜ್ಯವಲ್ಲದ p = 9ಕ್ಕೆ, a (9-1)/2 + 1 ಅನ್ನು 9ರಿಂದ ಭಾಗಿಸುವಂತಹ ಯಾವುದೇ a ಇಲ್ಲ. 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153. ತಿಳಿದಿರುವ ಅತಿದೊಡ್ಡ ಪ್ರಥಮ ಅವಿಭಾಜ್ಯವು 9,383,761 ಅಂಕಿಗಳ ಉದ್ದವಾಗಿದೆ. ಇದನ್ನು 2016ರ ನವೆಂಬರ್ 6ರಂದು ಘೋಷಿಸಿದ ಪ್ರೈಮ್ ಗ್ರಿಡ್ ಸ್ವಯಂಸೇವಕ ಕಂಪ್ಯೂಟಿಂಗ್ ಯೋಜನೆಯಲ್ಲಿ ಪೀಟರ್ ಸ್ಜಾಬೋಲ್ಕ್ಸ್ ಕಂಡುಹಿಡಿದರು. ಇದು ಮೆರ್ಸೆನ್ನೆಯಲ್ಲದ ಅತಿದೊಡ್ಡ ಅವಿಭಾಜ್ಯ ಮತ್ತು ಅತಿದೊಡ್ಡ ಕೋಲ್ಬರ್ಟ್ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಪ್ರೈಮ್ ಗ್ರಿಡ್ ಕಂಡುಹಿಡಿದ ಎರಡನೇ ಅತಿದೊಡ್ಡ ಮೊದಲ ಅವಿಭಾಜ್ಯವಾಗಿದೆ. ಈ ಪ್ರಮೇಯದ ಪುರಾವೆಯು ಪಾಕ್ಲಿಂಗ್ಟನ್-ಲೆಹ್ಮರ್ ಪ್ರಾಥಮಿಕತೆಯ ಪರೀಕ್ಷೆಯನ್ನು ಬಳಸುತ್ತದೆ ಮತ್ತು ಪೆಪಿನ್ನ ಪರೀಕ್ಷೆಯ ಪುರಾವೆಯನ್ನು ನಿಕಟವಾಗಿ ಹೋಲುತ್ತದೆ. ಈ ಪುರಾವೆಯನ್ನು ರಿಬೆನ್ಬೋಯಿಮ್ ಅವರ ಪುಸ್ತಕದ 52ನೇ ಪುಟದಲ್ಲಿ ಉಲ್ಲೇಖಗಳಲ್ಲಿ ಕಾಣಬಹುದು. ಇತಿಹಾಸ ಫ್ರಾಂಕೋಯಿಸ್ ಪ್ರೋಥ್ (1852-1879) ಈ ಪ್ರಮೇಯವನ್ನು 1878ರಲ್ಲಿ ಪ್ರಕಟಿಸಿದರು. ಪೆಪಿನ್ಸ್ ಟೆಸ್ಟ್ (ವಿಶೇಷ ಪ್ರಕರಣ k = 1, ಅಲ್ಲಿ ಒಬ್ಬರು a = 3 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತಾರೆ) ಅನ್ನು ಸಹ ನೋಡಿ.