Can Fermat's Little Theorem Simplify Prime Number Computations?

  • Thread starter Thread starter acarchau
  • Start date Start date
  • Tags Tags
    Theorem
AI Thread Summary
Fermat's Little Theorem states that for a prime p, a^(p-1) ≡ 1 (mod p). This leads to the conditions a^((p-1)/2) ≡ 1 (mod p) or a^((p+1)/2) ≡ -1 (mod p) when p-1 is even. The discussion seeks to identify special cases where determining which condition holds can be simplified, minimizing computational effort. The Jacobi symbol is referenced as a potential tool for this analysis. Understanding these conditions can enhance the efficiency of prime number computations.
acarchau
Messages
21
Reaction score
0
From fermat's little theorem we have for a prime to a prime p : a^{p-1}\equiv 1(mod p). Assuming p-1 to be even we must have either a^{\frac{p-1}{2}}\equiv 1 (mod p) or a^{\frac{p+1}{2}}\equiv -1 (mod p). Are there any special cases in which it is easy to determine which of the previous two conditions holds without a lot of compution?
 
Last edited:
Mathematics news on Phys.org
thank you!
 
Thread 'Video on imaginary numbers and some queries'

Thread 'Video on imaginary numbers and some queries'

Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »
Thread 'Unit Circle Double Angle Derivations'

Thread 'Unit Circle Double Angle Derivations'

Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
View full post »

Similar threads

A Prime Number Powers of Integers and Fermat's Last Theorem
Replies
1
Views
2K
What is Fermat's little theorem
Replies
1
Views
2K
I Questions regarding Kurepa's Conjecture
Replies
1
Views
2K
Insights Fermat's Last Theorem
3
Replies
105
Views
6K
B Fermat's little theorem proof?
Replies
1
Views
2K
MHB How can we use hints to prove divisibility of Fibonacci numbers?
Replies
1
Views
2K
B Calculating the coprime probability of two integers in a different way
Replies
13
Views
2K
If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....
Replies
16
Views
3K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
Replies
17
Views
3K
MHB How Does Modulo Arithmetic Prove a Combinatorial Identity Involving Primes?
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top