My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
  • 1 Post By agentredlum
Reply
 
LinkBack Thread Tools Display Modes
March 12th, 2017, 05: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?
mobel is offline  
 
March 12th, 2017, 10: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.
mobel is offline  
March 12th, 2017, 02:21 PM   #3
Math Team
 
agentredlum's Avatar
 
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
agentredlum is offline  
March 12th, 2017, 02:44 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 1,639
Thanks: 415

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 02:55 PM.
Maschke is online now  
March 12th, 2017, 03:13 PM   #5
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by Maschke View Post
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.
mobel is offline  
March 12th, 2017, 03: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.
mobel is offline  
March 12th, 2017, 03:58 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 1,639
Thanks: 415

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 04:06 PM.
Maschke is online now  
March 12th, 2017, 04: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.
mobel is offline  
March 18th, 2017, 04: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,..n-1 (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?
billymac00 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 08:59 AM
This conjecture is equivalent to the Goldbach's conjecture miket Number Theory 3 May 21st, 2014 11:22 PM
Conjecture on cycle length and primes : prime abc conjecture miket Number Theory 5 May 15th, 2013 06:35 PM
Enchev's conjecture - Goldbach's conjecture for twin pairs enchev_eg Number Theory 30 September 28th, 2010 09:43 PM
Yet (another) conjecture brunojo Number Theory 4 February 27th, 2009 07:27 AM





Copyright © 2017 My Math Forum. All rights reserved.