Coprime

Hello,

I am wondering how to go about beginning this proof. I initially tried to get something of the form ax+by=1 to prove the gcd is one, but couldn't get there. I was wondering if someone could point me in the right direction.

Suppose that a, b € Z are not both zero. Prove that a and b are coprime if and only if a and b form the first column of a two by two matrix with integer entries that has inverse with integer entries.

Been stuck with this one for a bit. Nothing on the internet seems to point me in the right direction. The only progress I've been able to do is use Bézout's theorem to show that since a and b are coprime, there is a solution to ma + nb = 1, and in the case gcd(1, a + b) = 1 which divides m - n no matter what, but this seems trivial, and I don't know how to actually get to the case where ma + nb is not equal to 1.

Hey there!

I know I need to use the Euler-Phi function to answer this question and I've calculated that phi(30) = 8. How can I incorporate the 120?

I thought about doing something with the fact that 120 = 30*2^2 but I don't really know what.

Thanks in advance :)

I tried to prove this statement via induction over n but I cannot see how I can show the implication

20n+3 and 15n+1 are coprime => 20(n+1)+3 = 20n + 23 and 15(n+1)+1 = 15n + 16 are coprime.

Is this the right approach? Or could the statement be proved in a different way? Thanks!

The idea of doing multiple Vigenere encryptions isn't new, however, I wanted to see how far I could take the security and practicality of the idea with minimal changes to keep it well within the realm of paper and pencil.

In short, the algorithm is a monoalphabetic substitution followed by two Vigenere encryptions with random coprime length keys followed by another substitution. Once the message is encrypted, the keys are themselves encrypted using a shared secret by the same process, and this encrypted key is sent with the encrypted message.

Strengths and weaknesses of this design are discussed after the full description and example.

Prep

• Shared Secret: 15 characters from a scrambled alphabet, split into two keys of lengths 7 and 8 (memorized by the communicating parties) (can be reused as often as desired)

    SS: MIFBKXW ERNJOVZG

• Message Keys: 1 scrambled alphabet and 1 string of random characters of length one more than the alphabet (standard lengths are 26 and 27) (random for each message)

    K1: GIZYNOEVBPSDTCWKXAQMUJHLFR
    K2: ARBSYDWADKFZEWBKDYFLYNOYNMR

• Make sure plaintext is no longer than the length of the two key lengths multiplied together (for 26 character alphabets, this max length is 26 x 27 = 702, about 2.5 tweets in length)

Encryption algorithm:

1. Substitution of plaintext through the first message key:

        ABCDEFGHIJKLMNOPQRSTUVWXYZ |   Plaintext: WHENINTHECOURSEOFHUMANEVENTSITBE...
                              |                   |
                              V                   V
    K1: GIZYNOEVBPSDTCWKXAQMUJHLFR | Substituted: HVNCBCMVNZWUAQNWOVUTGCNJNCMQBMIN...

2. Generation of keystream by doing vig (addition modulo) on the two keys being repeated (this can be done first if you like):

    K1 (repeating): GIZYNOEVBPSDTCWKXAQMUJHLFRGIZYNOEVBPSDTCWKXAQMUJHLFRGIZYNOEVBP...
                    +
    K2 (repeating): ARBSYDWADKFZEWBKDYFLYNOYNMRARBSYDWADKFZEWBKDYFLYNOYNMRARBSYDWA...
                    =
         Keystream: GZAQLRAVEZXCXYXUAYVXSWVJSDXIQZFMHRBSCISGSLHDORFHUZDESZZPOGCYXP...

3. Doing vig on the substituted plaitnext to generate the final ciphertext:

       PT (subbed): HVNCBCMVNZWUAQNWOVUTGCNJNCMQBMINZWTNQCNZNQQGAFOWAWCNKNWKDNMW...
                    +
         Keystream: GZAQLRAVEZXCXYXUAYVXSWVJSDXIQZFMHRBSCISGSLHDORFHUZDESZZPOGCY...
                    =
    Pre-Ciphertext: NUNSMTMQRYTWXOKQOTPQYYISFFJYRLNZGNUFSKFFFBXJOWTDUVFRCMVZRTOU...
``

I'm working on a proof that

gcd(Fn,Fn−1)=1 for all n greater than or equal to 0.

Here's what I have so far.

I used a proof by induction. I used

gcd(1,0)=1for the base case.

For the inductive step I assumed

gcd(Fn,Fn−1)=1

and set up

gcd(Fn+1,Fn)

=gcd(Fn,Fn+1modFn)

=gcd(Fn,(Fn+Fn−1)modFn)

I'm a bit confused about what to do at this step. Do I use

gcd(a+b,b)=gcd(a,b)? If so, how do I prove that? Would appreciate some help!

I'm learning the RSA Encryption algorithm and I can't find a way to quickly find coprime numbers to make the encryption lock key (e).

Working example:

I pick two prime numbers: 2 and 7

p = 2, q = 7

I multiply p and q and get 14. 14 is going to be my modulus number (n)

n = 14

Now I need to find how many numbers have common factors that won't make the number 14. This is not counting the number 1.

factors of 1 = 1
factors of 2 = 1, 2
factors of 3 = 1, 3
factors of 4 = 1, 2, 4
factors of 5 = 1, 5
factors of 6 = 1, 2, 3, 6
factors of 7 = 1, 7
factors of 8 = 1, 2, 4, 8
factors of 9 = 1, 3, 9
           10 = 1, 2, 5, 10
           11 = 1, 11
           12 = 1, 2, 3, 4, 6, 12	
           13 = 1, 13
           14 = 1, 2, 7, 14

1,3,5,9,11 and 13 have factors that can't make 14. There are 6 numbers.

A different way of finding 6 is to use Phi φ.

φ(n) = (p - 1)(q - 1)
     = 1 * 6
     = There are 6 numbers.

In order for my encryption key (e) to be valid, it needs to be:

1. Between two numbers: (1 < e < φ(n))  
2. Coprime with: n, φ(n)

There are only 4 numbers between 1 and 6 so it is easy to write them out:

1. 
    2, 3, 4 and 5

2. 
    2 has common factor with n? Yes - 2
    3 has common factor with n? No, has common factor with φ(n)? Yes - 3
    4 has common factor with n? Yes - 2
    5 has common factor with n? No, has common factor with φ(n)? No

Number 5 is the only number between 1 and 6 and it is coprime with n and φ(n)

e = 5

my RSA encryption lock = (e, n) = (5, 14)

Now my problem is that if I redo this example, but using bigger prime numbers for p and q, it becomes a really slow process to choose (e).

The encryption key (e) has to be between (1 < e < φ(n)).

How can I quickly find e if φ(n) is a number much bigger than 6 used in the above example? For example 223?

I only know how to do this if I write down every single number between 1 and 223 and then do what I did above:

If n = 233:
    1 has common factor with n? and has common factor with φ(n)?
    2 has common factor with n? and has common factor with φ(n)?
    3 has common factor with n? and has common factor with φ(n)?
    ...
    233 has common facto

Not sure if this should go here or on some other sub (maybe something to do with comp sci?), but here goes!

I'm trying to make my own rsa encryption library and I'm having trouble with part of the algorithm.

Here's what is giving me trouble: given two natural numbers, P and Q, I need to find E such that 1<E<(P-1)(Q-1) and E is coprime with both P*Q and (P-1)(Q-1).

It may help (to speed up typing) if (P-1)(Q-1) is shortened to Phi and P*Q is shortened to C, but that's just the notation I used in my program.

Any ideas of an algorithm (or a place to look for an algorithm) to find E?

Thanks in advance!

For weekly #11, coprimes are the subject. Detect if two values are coprime in different settings.

Given values, find if they are coprime or not.

>This is a community thing that happens every week. This is a casual affair, so feel free to participate or not at your discretion. General rules dictate people have a go at it themselves for the first 4 days, then we share solutions for another 3, but it's loose.

Check

Match

Chain

Here's a google drive of all current weekly puzzles.

Previous Community Weeklies:

• #1: File Copier
• #2: Logic Gate Simulation
• #3: Median
• #4: Pareto Frontier
• #5: Cold Storage Robot
• #6: Missing in Range
• #7: Frequency Tables
• #8: Mean
• #9: Permutations
• #10: Password

If you want to take a week, feel free to poke me about it.

φ stands for the Euler's totient function

Hey guys, so I am investigating affine ciphers and was wondering why in the formula E(x) = (ax+b) mod 26, a must be coprime to 26. I managed to prove that if a and 26 are coprime then there must be a value of x between 0 and 26 such that (ax)mod 26 = 0, and it clearly repeats itself after that. However the problems I'm having is how to prove or explain why it repeats, and also how to deal with the b. I know it's a shift, but I can't comprehend just why the same proof applies to a shift. Also, what will happen if a>26? This is really confusing to me, and an explanation would be tremendously helpful. Thank you guys so much.

Hi guys, I need some help:

the probability that two numbers are "coprimes" (ie it is not a common factor, such as 6 and 5 for example) is 6 / (pi ^ 2). I would like to create a program in C that, taken 100 pairs of numbers randomly generated, calculates pi through this probability.

I have two questions:

1. is there a formula (or even better, a program already written) that allows to see if two numbers are coprimes?

2. Is there a command to generate pairs of random numbers? I'm pretty new to the world of C programming but I'm curious to see the result

When they're also prime. For example are 7 with 7 coprime? They don't have any common divisors other than 1 and 7 but I'm not sure if you're also supposed to take the number itself or not as a divisor in this edge case

There is some way to say that two numbers are coprimes using congruence?

https://i.imgur.com/UmYKSXk.png

# The probability that two integers are coprime is 6 / pi^2
# 	x = 6/pi^2
#	pi = sqrt(6/x)
# --- 
#	we generate a series of random integers
#   test for coprimality
#   and collect the results to calculate the probability x


import random
import math
import fractions

# The maximum value for our integer pairs
max_val = 1000000
# The number of pairs to test for coprimality
pairs = 10000

cofactors_tally = 0.0
coprimes_tally = 0.0
  
# Generate random pairs of integers, test them for coprimality
for i in range(pairs):
	a = random.randint(1, max_val)
	b = random.randint(1, max_val)
	if fractions.gcd(a, b) == 1: coprimes_tally += 1
	else: cofactors_tally += 1

print "Coprimes:   ", coprimes_tally
print "Cofactors:  ", cofactors_tally
print "--"

# The probability based on our tests. 
P = coprimes_tally / pairs
print "Probability:", P

# estimate pi 
pi = math.sqrt(6.0/P)

print pi

Is there a proof for n,n+1 bring coprime?

I was exploring weird ways to get numbers from other numbers and realized that in all of the numbers I've checked (about 2-150) no two following numbers were coprime

Problem: If gcd(a, b)=1 then gcd(a+ab, b)=1

Hi guys. I'm relly stuck in the proof of the problem above. I don't know where to go from the gcd(a, b)=1. All I know is that the linear combination of it is ax+by=1 and a and b are coprimes. We don't have any topics about modulo yet and are only using definitions and properties of gcd and coprimes Someone please help. Thank you. :)

It is known that the probability of two randomly chosen integers being coprime is 6/π^(2). [I know that this is slightly non-rigorous].

I already know the proof of this theorem (that probability turns out to be the inverse of ζ(2), whose value is 6/π^(2)), but I'd like to ask if anyone know of an "intuitive" reason for why π should appear in such a question.

Let N be an natural number, and let P(N) be the probability that two distinct natural numbers less than N selected uniformly at random are coprime – that is, that they share no common factors. In the limit as N approaches infinity, what value does P(N) approach?

Question was so small, I included it in the title. Thanks in advance for any kind of help!

Edit: Of course a, b, s and t are integers

I asked a question on math.stackexchange, but will ask here too, but I'm also lazy, so here is the link.

Thanks in advance if anyone will/can help me.

Hannah has decided she is going to count down from some positive integer N, saying each integer aloud along the way. Herman would would also like to count down from some positive integer M, and will start at the exact same time as Hannah. They both say one integer aloud each second at the exact same time, until one of them runs out of positive integers to say and they both stop. Herman has decided he wants to choose M such that the amount of times Herman and Hannah simultaneously say two numbers that are coprime is maximized.

After a bit of thought he realized that this problem was too easy, so he decided he can only choose an M in the range from 1 to N-2 inclusive. He likes counting, so he wants to choose the largest possible M that satisfies these conditions.

Herman probably should have paid more attention in math class, because he can't figure this simple problem out! Can you help him choose M?

Info

Here is a brute force solution for N=5 (not really a hint, it's for if you have trouble understanding the problem).

Your goal is to give an efficient way to find M (not the obvious checking every number). Cases around N = 10^6 should be solvable by a human using the allowed resources below. Cases near 10^14 can still be solved in less than a second using a computer program (bonus points if you write one!). Actually, a human could still probably solve 10^14 within an hour using the resources.

Resources

You are allowed to reference lists of prime numbers, reference lists of prime factorizations, and use a GCD calculator.

If you're solving by hand try to find f(10), f(10^(3)), and f(10^(6)). I won't mark this as solved unless a proof of correctness is provided. Good luck!

Hello. I'm having some trouble proving this. I'm guessing that the proof uses the homomorphism theorem, but I'm still kind of stuck, so any tips would be appreciated. Thanks in advance

I was thinking about smooth numbers, and I wondered if every integer could be represented as the difference between two 3-smooth numbers. I think this is equivalent to whether numbers coprime to both 2 and 3 could be written as the difference between a power of 2 and a power of 3. Anyone know anything about this?

This question came up while thinking about something totally unrelated. It might be easy, but I'm not quite sure:

Fix N a natural number. What is the largest size of a subset S of {1,...,N} such that the difference between any two elements of S is coprime to N?

I'm really interested in the odd case N=2k+1. I'd love for the following to be true:

There exists a linear function f satisfying the following. For any odd natural number N=2k+1, there exists a subset S of {1,...,N} whose cardinality is at least f(N), such that pairwise differences taken from S are all coprime to N.

I care about asymptotics, so I'd also be fine with replacing "For any odd natural number...." with "For all but finitely many odd numbers..."

Thanks for reading

Edit: Of course the way that I've stated it, if this is true for all but finitely many odd numbers, it's also true for all odd numbers, so this focus on asymptotics is already encoded by the original statement.

Bonus points to those who derive an explicit formula.

I'll post a solution later today. Have fun!

EDIT: The solution, as some of you have pointed out, is 2*10^19. For n>1, general formula is given by n\phi(n)/2, which can be observed in several ways. The simplest perhaps is to show that (n,k)=1 iff (n-k,n)=1 and sum the terms in pairs (noting that n/2 will never be included). Thus we have \phi(n)/2 pairs, each of which sum to n.

There is another way, using convolutions, which can be used to prove the the fact that [; 2\sum_{\substack{k=1 \\ (k,n)=1}}^n k/n ;] is a multiplicative function (when redefined at 1). Evaluated at prime powers shows that it is equal to the Euler phi function. From this we can simply multiply by n/2. This method, while longer, adapts for a more general technique.

Not a homework problem, this genuinely stumped me. Perhaps someone with programming or higher-level experience could pitch in?

Hi everyone. I'm trying to write a proof on if various number pairs are coprime, but I'm not sure how to go about proving it. We have the definition that numbers a and b are coprime iff their only common divisor of both of them is +/- 1. So, the first question they give is the numbers 30 and 17.

I know that there exists an integer S such that 30 = nS, and there exists an integer T such that 17 = nT, as this is the definition of divisiblity. But how do I continue from here to prove their only common divisor is +/- 1?

Thanks!

Problem: If gcd(a, b)=1 then gcd(a+ab, b)=1

Hi guys. I'm relly stuck in the proof of the problem above. I don't know where to go from the gcd(a, b)=1. All I know is that the linear combination of it is ax+by=1 and a and b are coprimes. We don't have any topics about modulo yet and are only using definitions and properties of gcd and coprimes Someone please help. Thank you. :)