[Number Theory] Proving 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.

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.

👍︎ 2
💬︎
📅︎ Feb 06 2021
🚨︎ report
Let a,b be coprime integers. Prove that gcd(ma + nb, a + b) Divides m-n for any integers m,n

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.

👍︎ 2
💬︎
📅︎ Mar 13 2021
🚨︎ report
Find the number of integers a with 1 <= a <= 120 which are not coprime to 30.

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.

👍︎ 2
💬︎
📅︎ Jan 30 2021
🚨︎ report
[Elementary Number Theory] How can I show that 20n+3 and 15n+1 are coprime for each natural number n?

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!

👍︎ 2
💬︎
📅︎ Jul 30 2020
🚨︎ report
Tuvig (coprime length Vigenere encryption with some tweaks) (and a challenge with \$ rewards)

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

• 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...

1. 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...
+
=
Keystream: GZAQLRAVEZXCXYXUAYVXSWVJSDXIQZFMHRBSCISGSLHDORFHUZDESZZPOGCYXP...

1. Doing vig on the substituted plaitnext to generate the final ciphertext:
       PT (subbed): HVNCBCMVNZWUAQNWOVUTGCNJNCMQBMINZWTNQCNZNQQGAFOWAWCNKNWKDNMW...
+
Keystream: GZAQLRAVEZXCXYXUAYVXSWVJSDXIQZFMHRBSCISGSLHDORFHUZDESZZPOGCY...
=
Pre-Ciphertext: NUNSMTMQRYTWXOKQOTPQYYISFFJYRLNZGNUFSKFFFBXJOWTDUVFRCMVZRTOU...

... keep reading on reddit ➡

👍︎ 17
💬︎
📅︎ Jun 07 2020
🚨︎ report
(Discrete Math) Prove consecutive fibonacci numbers are coprime

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!

👍︎ 2
💬︎
📅︎ Sep 23 2020
🚨︎ report
Recreating the polar plot of primes with the coprime residue classes colored
👍︎ 213
💬︎
📅︎ Jan 16 2020
🚨︎ report
How can I know if a system of congruences that hasn't coprime modules, has solutions?
👍︎ 10
💬︎
👤︎ u/allexj
📅︎ May 23 2020
🚨︎ report
Calculating coprime numbers when working with RSA Encryption algorithm.

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 &lt; e &lt; φ(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
... keep reading on reddit ➡

👍︎ 2
💬︎
📅︎ Jan 30 2020
🚨︎ report
How can I find a third coprime (as applied to RSA encryption)?

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?

👍︎ 2
💬︎
📅︎ Dec 04 2019
🚨︎ report
Coprime Integers
👍︎ 26
💬︎
📅︎ Sep 19 2019
🚨︎ report
how can I prove the existence of k,m such that A^k=mB+1 for all coprime A,b?
👍︎ 4
💬︎
📅︎ May 01 2019
🚨︎ report
Exapunks Community Weekly #11: Coprime Pairs

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

Previous Community Weeklies:

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

👍︎ 6
💬︎
📅︎ Jan 19 2019
🚨︎ report
If n and m are coprimes integers, why φ(n)*φ(m)=φ(n*m)

φ stands for the Euler's totient function

👍︎ 5
💬︎
📅︎ Apr 26 2019
🚨︎ report
Can someone explain to me why the key must be coprime to 26 in Affine ciphers?

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.

👍︎ 10
📰︎ r/math
💬︎
📅︎ Nov 12 2016
🚨︎ report
Calculate pi from coprimes

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

👍︎ 3
💬︎
📅︎ Mar 29 2019
🚨︎ report
Are equal numbers considered to be coprime?

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

👍︎ 6
💬︎
📅︎ Mar 22 2019
🚨︎ report
Coprimes and congruence question

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

👍︎ 8
📰︎ r/math
💬︎
📅︎ Dec 30 2017
🚨︎ report
Estimating pi using the probability that two integers are coprime.

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
👍︎ 14
📰︎ r/math
💬︎
📅︎ Jan 10 2018
🚨︎ report
Coprime numbers

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

👍︎ 2
💬︎
📅︎ Jul 01 2017
🚨︎ report
Church of Satoshi forgets which public-key cryptography algorithm Bitcoin uses, praises random guy for factoring a three-digit coprime. np.reddit.com/r/Bitcoin/c…
👍︎ 14
💬︎
📅︎ May 17 2015
🚨︎ report
[Number Theory] GCD and coprimes

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. :)

👍︎ 2
💬︎
📅︎ Mar 19 2017
🚨︎ report
Intuition behind \pi appearing in the probability of two randomly chosen integers being coprime.

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.

👍︎ 11
📰︎ r/math
💬︎
📅︎ Sep 15 2016
🚨︎ report
Coprime Probability

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?

👍︎ 4
💬︎
📅︎ Jan 23 2015
🚨︎ report
[Numbers Theory] How to prove for all possible coprimes a,b there exist s and t so as a*s + B*t = 1

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

👍︎ 2
💬︎
📅︎ Jan 14 2018
🚨︎ report
[University algebraic-geometry]The intersection multiplicity of two coprime polynomials is less or equal than the multiplicity of their product?

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.

👍︎ 2
💬︎
📅︎ May 29 2015
🚨︎ report
Coprime Countdown

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!

👍︎ 2
💬︎
📅︎ Aug 13 2015
🚨︎ report
[Abstract Algebra] If |H| is coprime with ([G:H]-1)!, then H is normal.

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

👍︎ 5
💬︎
📅︎ Jan 28 2018
🚨︎ report
Can every integer coprime to 6 be represented as the difference between a power of 2 and a power of 3?

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?

👍︎ 7
📰︎ r/math
💬︎
👤︎ u/pTea
📅︎ Jun 07 2013
🚨︎ report
How large of a subset of {1,...,N} can you form such that all pairwise differences are coprime to N?

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..."

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.

👍︎ 2
📰︎ r/math
💬︎
📅︎ Jun 27 2013
🚨︎ report
From a set of ten consecutive integers, a subset is chosen such that every integer that is coprime to every other integer in the set is present in the subset. What are the possible sizes of the subset? cotpi.com/p/41/
👍︎ 6
💬︎
👤︎ u/cotpi
📅︎ Feb 27 2012
🚨︎ report
Give the sum of the positive integers less than 10^10 that are coprime to 10^10.

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.

👍︎ 10
💬︎
📅︎ Jan 22 2011
🚨︎ report
Find coprime a, b such that (a+b) divides a^2+b^2?

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

👍︎ 6
📰︎ r/math
💬︎
📅︎ Feb 09 2015
🚨︎ report
Prove if two numbers are coprime

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!

👍︎ 2
💬︎
📅︎ Mar 08 2015
🚨︎ report
Can you find an upper bound for the length of the cycle in the decimal expansion of the rational number m/n (where m and n are coprime natural numbers)?
👍︎ 4
💬︎
📅︎ Nov 05 2012
🚨︎ report
[Number Theory] GCD and Coprimes

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. :)

👍︎ 4
💬︎
📅︎ Mar 19 2017
🚨︎ report