My Math Forum Conjecture

 Number Theory Number Theory Math Forum

 March 12th, 2017, 04:01 AM #1 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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^2-1 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 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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. Thanks from mobel
 March 12th, 2017, 01:44 PM #4 Senior Member   Joined: Aug 2012 Posts: 2,043 Thanks: 583 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
Banned Camp

Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
 Originally Posted by Maschke 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
It does not work for 11
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 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 To find a multiplicative inverse mod n I will suggest you to read this article : https://f56df077-a-62cb3a1a-s-sites....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: 2,043 Thanks: 583 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 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 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 semi-primes. m=91 (semi-prime 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

 Tags conjecture

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post MrAwojobi Number Theory 66 June 2nd, 2014 07:59 AM miket Number Theory 3 May 21st, 2014 10:22 PM miket Number Theory 5 May 15th, 2013 05:35 PM enchev_eg Number Theory 30 September 28th, 2010 08:43 PM brunojo Number Theory 4 February 27th, 2009 06:27 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top