{"entities":{"Q1198983":{"pageid":1209732,"ns":120,"title":"Item:Q1198983","lastrevid":80355587,"modified":"2026-05-06T16:00:31Z","type":"item","id":"Q1198983","labels":{"en":{"language":"en","value":"Effective primality tests for integers of the forms \\(N=k3^ n+1\\) and \\(N=k2^ m3^ n+1\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 93333"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$68159CC2-6C7E-49DD-A861-AB827D8CDD60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8aa154f523c6dd46ed9a9946aa292fae648fb6fa","datavalue":{"value":{"text":"Effective primality tests for integers of the forms \\(N=k3^ n+1\\) and \\(N=k2^ m3^ n+1\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198983$22A510F2-6F45-4F9E-AB75-9A8E5826724D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26741a7bbda1f97a1caa32f62c765ce83bf1d57e","datavalue":{"value":"0772.11002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198983$7917641A-F1F0-4026-AFCD-3A10B82B08DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"911f6f7b4253d3e57b5971664cd526ed010104ba","datavalue":{"value":"10.1007/BF02074886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198983$C11CC92B-55F2-4941-A61B-B9CEC5500044","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c79c9b2487924251034fd44b80fe1302b400b709","datavalue":{"value":{"entity-type":"item","numeric-id":213202,"id":"Q213202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$FA104EEE-447A-4DA1-B497-87BA27F154A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$BA5C3768-9CFA-4C75-AD9D-297C76FF188C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198983$47EC44B3-E2CB-445A-B38F-842B2E0FDB0B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e013300be7abb663894f13a5b0e50118ba703647","datavalue":{"value":"The well-known primality testing theorem of Proth states that if \\(N\\) is an integer of the form \\(N=k\\cdot 2^ n+1\\), where \\(k\\) is odd and \\(0<k<2^ n\\), and if \\(a\\) is an integer such that \\((a/N)=-1\\) (where \\((a/N)\\) is the usual Jacobi symbol), then \\(N\\) is prime if, and only if \\(a^{(N-1)/2}\\equiv-1\\bmod N\\).   In this paper an analogous theorem is proved for integers \\(N\\) of the form \\(N=k\\cdot 3^ n+1\\), where \\(k\\) is even and not divisible by 3 and \\(0<k<3^ n-2\\). In the proof use is made of elementary facts about the arithmetic in \\(\\mathbb{Z}[\\omega]\\), where \\(\\omega\\) is a primitive third root of unity. This theorem is combined with Proth's theorem to give a primality test for integers of the form \\(N=k\\cdot 2^ m 3^ n+1\\). Like Proth's test, the tests given here are polynomial in \\(\\log N\\). The tests are applied to two examples, viz., \\(N=40\\cdot 3^{543}+1\\) and \\(N=5\\cdot 2^{54} 3^{57}+1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198983$57DD8DAD-9363-4A0B-BECE-53AF3C5728B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f5492126398e1ddf0e8e00d7285568c890b3f47","datavalue":{"value":"11A51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198983$4EBFECA0-A80A-4279-8BE0-26836231F3BB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e6f2e3faa734832a22bc7a2fddd3ace8ae1bb7cd","datavalue":{"value":"93333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198983$F4DF2673-5CAD-430D-897D-E20F917D9762","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d6fb9f89a04e863884a5a23a96811f29b807e11","datavalue":{"value":"Proth's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198983$B28AEF64-0F5F-4A5E-8F2E-D2A74B771652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efed5172d86eecab432335e1eeacd0424f509637","datavalue":{"value":"primality test","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198983$C14B8E6E-369A-4FE3-B5D8-514C31D8E179","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$CCAE82BD-354B-4AF1-8B9A-5B80F8DEB67C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"045f069d44b7d32ac907d01f81c962bc393253fb","datavalue":{"value":{"entity-type":"item","numeric-id":3939864,"id":"Q3939864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$015DBE27-EBBC-4AD9-86DE-F408E9EEFB81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f28cff96c4c0fcad4aad18ce0eb8e44554153cbf","datavalue":{"value":{"entity-type":"item","numeric-id":5902990,"id":"Q5902990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$02E3BE49-6ABC-412E-A127-9052A6D59971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87de9755dc0cc2f89ed93d922df74ca099c022c0","datavalue":{"value":{"entity-type":"item","numeric-id":3246495,"id":"Q3246495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$4FF293FE-1105-497C-8ED0-1273E88EB33B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"403b3c2aec72ee72429900f10e7f1fb67f59554d","datavalue":{"value":{"entity-type":"item","numeric-id":5675776,"id":"Q5675776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198983$ABE870BD-6F44-492A-A913-29B7C0BDFA60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9f4069af0a49d8201c99f23019959e98ba3de740","datavalue":{"value":"https://doi.org/10.1007/bf02074886","type":"string"},"datatype":"url"},"type":"statement","id":"Q1198983$A25A4D14-679C-4F54-B22D-9654D26EE79B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a9776c6d222be7418fcefd80594f0c37fb47da70","datavalue":{"value":"W2039239222","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198983$936C6918-2328-4808-9E97-1DDF91D1DEAB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afcf7ae3283a3021c9754946972cf6155bfa853b","datavalue":{"value":{"entity-type":"item","numeric-id":3417332,"id":"Q3417332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0515139a7bf76d3c06caa4bbaf92cdd09ad55a78","datavalue":{"value":{"amount":"+0.8442365527153015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198983$9A22D975-32B2-477E-B43C-670F8E07AB23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b6cc6feb7a63a9e1d866921784bacdc487b1fce","datavalue":{"value":{"entity-type":"item","numeric-id":4429647,"id":"Q4429647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3dffc2dcff21b1ed6e1f4e1b7e7c68a311534dd","datavalue":{"value":{"amount":"+0.8439532518386841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198983$D02FAE06-9919-4B6E-8419-70ECDADE816C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79c9ffc856ecf163e633e9b0dd2edf8155223762","datavalue":{"value":{"entity-type":"item","numeric-id":2330377,"id":"Q2330377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"175e6f1938fe4f6f4960ea99da50b04126d19f35","datavalue":{"value":{"amount":"+0.84354168176651","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198983$BD7052E8-62FA-4A2C-954B-F494EC38C8D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68dd830723fdbea470122441ebbd5e23a362b2a3","datavalue":{"value":{"entity-type":"item","numeric-id":5951950,"id":"Q5951950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ad02286abfac3ca37ed0633b83b6b10eb3c805e","datavalue":{"value":{"amount":"+0.8276324272155762","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198983$0979C7CF-DCAF-4EBD-9C4D-C2D9E1BFF8CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d7290d04d5b8a4dd366bb96062c0d8e4961867e","datavalue":{"value":{"entity-type":"item","numeric-id":5497037,"id":"Q5497037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fdd9b34f9bcb27c7791c50ce849364105ae0908","datavalue":{"value":{"amount":"+0.8064565658569336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1198983$96959C69-BFD4-4E3F-BF26-B50591BD7A2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Effective primality tests for integers of the forms \\(N=k3^ n+1\\) and \\(N=k2^ m3^ n+1\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Effective_primality_tests_for_integers_of_the_forms_%5C(N%3Dk3%5E_n%2B1%5C)_and_%5C(N%3Dk2%5E_m3%5E_n%2B1%5C)"}}}}}