Talk:Strong coprimality

Should we distinguish between

$\scriptstyle k\,$ is left strongly coprime to $\scriptstyle n\,$ iff $\scriptstyle k\,$ is relatively prime to $\scriptstyle n,$ and $\scriptstyle k\,$ does not divide $\scriptstyle n-1\,$;

$\scriptstyle k\,$ is right strongly coprime to $\scriptstyle n\,$ iff $\scriptstyle k\,$ is relatively prime to $\scriptstyle n,$ and $\scriptstyle k\,$ does not divide $\scriptstyle n+1\,$;

$\scriptstyle k\,$ is very strongly coprime (or doubly strongly coprime) to $\scriptstyle n\,$ iff $\scriptstyle k\,$ is relatively prime to $\scriptstyle n,$ and $\scriptstyle k\,$ does not divide neither $\scriptstyle n-1\,$ nor $\scriptstyle n+1\,$.

— Daniel Forgues 23:21, 28 November 2010 (UTC)

Very strongly coprime to n

Very strongly coprime (or doubly strongly coprime) to n: numbers coprime to n but not divisors of n-1 or n+1

Very strongly coprime (or doubly strongly coprime) thus means simultaneously left strongly coprime and right strongly coprime.

    {k coprime to n}             - {k | (n-1)}    - {k | (n+1)}
    ________________             _____________    _____________  

1:  {1}                                           - {1,2}          = {}
2:  {1}                          - {1}            - {1,3}          = {}
3:  {1,2}                        - {1,2}          - {1,2,4}        = {}
4:  {1,3}                        - {1,3}          - {1,5}          = {}
5:  {1,2,3,4}                    - {1,2,4}        - {1,2,3,6}      = {}
6:  {1,5}                        - {1,5}          - {1,7}          = {} 
7:  {1,2,3,4,5,6}                - {1,2,3,6}      - {1,2,4,8}      = {5}
8:  {1,3,5,7}                    - {1,7}          - {1,3,9}        = {5}
9:  {1,2,4,5,7,8}                - {1,2,4,8}      - {1,2,5,10}     = {7}
10: {1,3,7,9}                    - {1,3,9}        - {1,11}         = {7} 
11: {1,2,3,4,5,6,7,8,9,10}       - {1,2,5,10}     - {1,2,3,4,6,12} = {7,8,9} 
12: {1,5,7,11}                   - {1,11}         - {1,13}         = {5,7}
13: {1,2,3,4,5,6,7,8,9,10,11,12} - {1,2,3,4,6,12} - {1,2,7,14}     = {5,8,9,10,11}
14: {1,3,5,9,11,13}              - {1,13}         - {1,3,5,15}     = {9,11}
15: {1,2,4,7,8,11,13,14}         - {1,2,7,14}     - {1,2,4,8,16}   = {11,13} 
16: {1,3,5,7,9,11,13,15}         - {1,3,5,15}     - {1,17}         = {7,9,11,13}

— Daniel Forgues 19:46, 5 August 2011 (UTC)

Left strongly coprime to n, right strongly coprime to n

Left strongly coprime to n: numbers coprime to n but not divisors of n-1

Left strongly coprime corresponds to strongly coprime as defined in User:Peter Luschny/StrongCoprimality.

    {k coprime to n}             - {k | (n-1)}    
    ________________             _____________    

1:  {1}                          - {1}              = {}                                           
2:  {1}                          - {1}              = {}          
3:  {1,2}                        - {1,2}            = {}          
4:  {1,3}                        - {1,3}            = {}          
5:  {1,2,3,4}                    - {1,2,4}          = {3}        
6:  {1,5}                        - {1,5}            = {}            
7:  {1,2,3,4,5,6}                - {1,2,3,6}        = {4,5}        
8:  {1,3,5,7}                    - {1,7}            = {3,5}           
9:  {1,2,4,5,7,8}                - {1,2,4,8}        = {5,7}       
10: {1,3,7,9}                    - {1,3,9}          = {7}         
11: {1,2,3,4,5,6,7,8,9,10}       - {1,2,5,10}       = {3,4,6,7,8,9}    
12: {1,5,7,11}                   - {1,11}           = {5,7}        
13: {1,2,3,4,5,6,7,8,9,10,11,12} - {1,2,3,4,6,12}   = {5,7,8,9,10,11}
14: {1,3,5,9,11,13}              - {1,13}           = {3,5,9,11}         
15: {1,2,4,7,8,11,13,14}         - {1,2,7,14}       = {4,8,11,13}     
16: {1,3,5,7,9,11,13,15}         - {1,3,5,15}       = {7,9,11,13}

Right strongly coprime to n: numbers coprime to n but not divisors of n+1

    {k coprime to n}             - {k | (n+1)}
    ________________             _____________  

1:  {1}                          - {1,2}          = {}                  
2:  {1}                          - {1,3}          = {}
3:  {1,2}                        - {1,2,4}        = {}
4:  {1,3}                        - {1,5}          = {3}
5:  {1,2,3,4}                    - {1,2,3,6}      = {4}
6:  {1,5}                        - {1,7}          = {5} 
7:  {1,2,3,4,5,6}                - {1,2,4,8}      = {3,5,6}
8:  {1,3,5,7}                    - {1,3,9}        = {5,7}
9:  {1,2,4,5,7,8}                - {1,2,5,10}     = {4,7,8}
10: {1,3,7,9}                    - {1,11}         = {3,7,9} 
11: {1,2,3,4,5,6,7,8,9,10}       - {1,2,3,4,6,12} = {5,7,8,9,10} 
12: {1,5,7,11}                   - {1,13}         = {5,7,11}
13: {1,2,3,4,5,6,7,8,9,10,11,12} - {1,2,7,14}     = {3,4,5,6,8,9,10,11,12}
14: {1,3,5,9,11,13}              - {1,3,5,15}     = {9,11,13}
15: {1,2,4,7,8,11,13,14}         - {1,2,4,8,16}   = {7,11,13,14} 
16: {1,3,5,7,9,11,13,15}         - {1,17}         = {3,5,7,9,11,13,15}

— Daniel Forgues 20:06, 5 August 2011 (UTC)

The set $\scriptstyle M\,$ of numbers which are very strongly coprime (or doubly strongly coprime) to $\scriptstyle n\,$ would thus be the intersection of the set $\scriptstyle M_{l}\,$ of numbers which are left strongly coprime to $\scriptstyle n\,$ and the set $\scriptstyle M_{r}\,$ of numbers which are right strongly coprime to $\scriptstyle n\,$. — Daniel Forgues 21:31, 5 August 2011 (UTC)

See also User talk:Peter Luschny/StrongCoprimality.

---

To avoid clones I suggest to continue the discussion on this page. Peter Luschny 21:58, 5 August 2011 (UTC)

Coprimorial of n / divisorial of n-1 provably always integer?

On User:Peter Luschny/StrongCoprimality, you say

Now, what is the ratio coprimorial / divisorial ? It turns out that we have to compare the coprimorial of n with the divisorial of n − 1 to get integer values.

Is coprimorial of $\scriptstyle n\,$ / divisorial of $\scriptstyle n-1\,$ provably always integer? Or is it conjectured from numerical evidence?

If $\scriptstyle n-1\,$ is a prime power, its obvious

If $\scriptstyle p^{k}\,$ exactly divides $\scriptstyle n-1\,$, then $\scriptstyle \{1,\,p,\,p^{2},\,\ldots ,\,p^{k}\}\,$ are obviously coprime to $\scriptstyle n\,$ and less than $\scriptstyle n\,$ (thus factors of the coprimorial of n). So if $\scriptstyle n-1\,$ is a prime power, then coprimorial of n / divisorial of n-1 is always integer. How do we go from here to prove that coprimorial of n / divisorial of n-1 is always integer?

Now, if $\scriptstyle n+1\,$ is a prime power, then

If $\scriptstyle p^{k}\,$ exactly divides $\scriptstyle n+1\,$, then $\scriptstyle \{1,\,p,\,p^{2},\,\ldots ,\,p^{k}\}\,$ are obviously coprime to $\scriptstyle n\,$, but $\scriptstyle p^{k}\,=\,n+1\,>\,n\,$ (thus not a factor of the coprimorial of n) if $\scriptstyle n+1\,$ is a prime power. So if $\scriptstyle n+1\,$ is the square of a prime, then coprimorial of n / divisorial of n+1 is not an integer, although (n+1) * coprimorial of n / divisorial of n+1 is an integer.

But then does the following hold?

Is (n+1) * coprimorial of n / divisorial of n+1 provably always integer?

If n+1 is a prime power, then it is obviously so. How would we go from here to prove that (n+1) * coprimorial of n / divisorial of n+1 is always integer?

— Daniel Forgues 18:13, 6 August 2011 (UTC)

About definition of strong coprimality

What was the incentive to define strong coprimality as

a is strongly prime to b (`a $\scriptstyle {\underline {\perp }}\,$ b´) iff a is prime to b and a does not divide b − 1.

instead of the more restrictive

a is strongly prime to b (`a $\scriptstyle {\underline {\perp }}\,$ b´) iff a is prime to b and a is prime to b − 1.

and the corresponding left strongly (a is prime to b − 1 and a is prime to b,) right strongly (and a is prime to b and a is prime to b + 1,) and very strongly (a is prime to b − 1, a is prime to b and a is prime to b + 1)?

— Daniel Forgues 18:25, 6 August 2011 (UTC)

About the "more restrictive definition"

With this more restrictive definition, one might then say

a is almost noncoprime to b (meaning a is noncoprime to b - 1)

and

a is quasi noncoprime to b (meaning a is noncoprime to b + 1)

and finally

a is nearly noncoprime to b (meaning a is noncoprime to b - 1 or a is noncoprime to b + 1)

One might then say

a is a very strongly coprime to b iff a is both coprime to b and not nearly noncoprime to b.

— Daniel Forgues 20:52, 6 August 2011 (UTC)

What about strong nondivisibility?

a is a strong nondivisor of b (`a $\scriptstyle {\underline {\nmid }}\,$ b´) iff a does not divide b and a does not divide b − 1.

or

a is a left strong nondivisor of b iff a does not divide b and a does not divide b − 1.

a is a right strong nondivisor of b iff a does not divide b and a does not divide b + 1.

and then

a is a very strong nondivisor of b iff a does not divide b, a does not divide b − 1 and a does not divide b + 1.

— Daniel Forgues 18:50, 6 August 2011 (UTC)

One might say

a almost divides b (or a is an almost divisor of b) meaning a divides b - 1

and

a quasi divides b (or a is a quasi divisor of b) meaning a divides b + 1

and finally

a nearly divides b (or a is a near divisor of b) meaning a divides b - 1 or a divides b + 1

One might then say

a is a very strong nondivisor of b iff a is neither a divisor of b nor a near divisor of b.

— Daniel Forgues 20:36, 6 August 2011 (UTC)

Only for the sake of completeness...

Only for the sake of completeness... I don't see the value... :)

a is a ???strong nondivisor??? of b iff a does not divide b and a is coprime to b − 1.

or

a is a ???left strong nondivisor??? of b iff a does not divide b and a is coprime to b − 1.

a is a ???right strong nondivisor??? of b iff a does not divide b and a is coprime to b + 1.

and then

a is a ???very strong nondivisor??? of b iff a does not divide b, a is coprime to b − 1 and a is coprime to b + 1.

— Daniel Forgues 18:50, 6 August 2011 (UTC)