March 12th, 2017, 04:01 AM  #1 
Senior Member Joined: Dec 2013 Posts: 1,101 Thanks: 40  Conjecture
Conjecture about prime numbers : For every positive integer n>29 it always exist at least one pair of prime numbers p and q (included the number 2) such as : p*q = 1 mod n p and q both < n Example n=30 p=7 < 30 q=13 < 30 7*13=91=1 mod 30 There are only 3 numbers <30 (2,11,29) not satisfying the 2 conditions above. There is a general form of n satisfying both conditions : n=p^21 where p is prime Example : 8=(3*3)1 3 < 8 9=1 mod 8 24=(5*5)1 5<24 25=1 mod 24 etc.... Any proof or counterexample? Is there a way to test quickly any n to check if it has a solution? 
March 12th, 2017, 09:09 AM  #2 
Senior Member Joined: Dec 2013 Posts: 1,101 Thanks: 40 
No counterexample yet? Maybe there is a proof (elementary?) that the conjecture is true. 
March 12th, 2017, 01:21 PM  #3 
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 
First I would like to say welcome back. I'm glad you are back. I will keep this interesting question in mind but my brain is mush right now. 
March 12th, 2017, 01:44 PM  #4 
Senior Member Joined: Aug 2012 Posts: 1,529 Thanks: 364 
Surely this would work for 11 and 29. To say $pq \equiv 1 \pmod n$ means that $p$ and $q$ are multiplicative inverses mod $n$. If $n$ is prime then everything other than $0$ or a multiple of $n$ is invertible in $\mathbb Z /n \mathbb Z$. For example $3$ and $4$ work mod $11$. In the general case you just have to find any invertible element in $\mathbb Z /n \mathbb Z$. It and its inverse will have representatives $< n$. An element is invertible if it's relatively prime to $n$. For example if $n = 100$ then all I have to do is find any number less than $100$ and relatively prime to it (other than $1$). For example $3$ would work. Then you just have to find the multiplicative inverse of $3$ mod $100$ and you're done. In this case $3$ doesn't divide $101$ but $3$ does divide $201$. Since $201 / 3 = 67$, your $p$ and $q$ are $3$ and $67$. Of course this solution is not unique, any pair of multiplicative inverses will do. To find a multiplicative inverse mod $n$ you can use the extended Euclidean algorithm. https://en.wikipedia.org/wiki/Extend...dean_algorithm Last edited by Maschke; March 12th, 2017 at 01:55 PM. 
March 12th, 2017, 02:13 PM  #5  
Senior Member Joined: Dec 2013 Posts: 1,101 Thanks: 40  Quote:
3 is prime <11 4 is not prime You need to read carefully my statement. It does work for 2 and 29 Otherwise you need to prove that it works any n>29. You did not until now.  
March 12th, 2017, 02:46 PM  #6 
Senior Member Joined: Dec 2013 Posts: 1,101 Thanks: 40 
To find a multiplicative inverse mod n I will suggest you to read this article : https://f56df077a62cb3a1assites....attredirects=0 I implemented it quickly on Excel it works very fine. 
March 12th, 2017, 02:58 PM  #7 
Senior Member Joined: Aug 2012 Posts: 1,529 Thanks: 364 
Oh primes, sorry. Good question. Comes down to whether we can always find a pair of multiplicative inverses mod $n$ that are themselves prime. Sounds like a hard problem offhand. Last edited by Maschke; March 12th, 2017 at 03:06 PM. 
March 12th, 2017, 03:44 PM  #8 
Senior Member Joined: Dec 2013 Posts: 1,101 Thanks: 40 
Both must be prime and less than n. So 2 conditions. Otherwise you will always find a solution with only one condition : both prime. It is linked to the factorization of odd semiprimes. m=91 (semiprime to factorize) Hence n=90 If 90 has 2 primes p and q as factors such as p*q=1 mod 90 then 91 has 2 factors (7 and 13 for example). The important question remaining unanswered is how to find p and q quickly (that is another problem). The conjecture must be proven true first. 
March 18th, 2017, 03:44 PM  #9 
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 338 Thanks: 4 Math Focus: primes of course 
Perhaps this is obvious but since p,q<n, the search zone for a solution boils down to k*n+1=pq where k=1,2,..n1 (as we know p*q must<n^2). So the conjecture will hold unless such a closed sequence never encounters a semiprime. So the required, equivalent proof is to show such a closed sequence must always contain a semiprime. Right? 

Tags 
conjecture 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Beal's Conjecture Conjecture  MrAwojobi  Number Theory  66  June 2nd, 2014 07:59 AM 
This conjecture is equivalent to the Goldbach's conjecture  miket  Number Theory  3  May 21st, 2014 10:22 PM 
Conjecture on cycle length and primes : prime abc conjecture  miket  Number Theory  5  May 15th, 2013 05:35 PM 
Enchev's conjecture  Goldbach's conjecture for twin pairs  enchev_eg  Number Theory  30  September 28th, 2010 08:43 PM 
Yet (another) conjecture  brunojo  Number Theory  4  February 27th, 2009 06:27 AM 