All Questions
17
questions
1
vote
2
answers
73
views
Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)
I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
1
vote
1
answer
61
views
Set of natural numbers related to least common multiple
I have come across the following set in my research, and I am curious whether this has been studied before/if there is a reference for a related construction.
Given a natural number $n$, let $S(n)$ be ...
-1
votes
1
answer
70
views
Suppose a, b are integers and LCM(a, b) = GCD(a, b)^2. What can be said about the prime decompositions of a and b? [duplicate]
Unsure how to approach the problem besides using the fact that the LCM(a,b) * GCD(a,b) = a*b. I see the implication that the GCD(a,b)^3 = a * b. Perhaps it means a and b are different powers of the ...
1
vote
0
answers
18
views
Factorization by order finding [duplicate]
Let $N$ be a composite integer and consider any $x\le N$. The order of $x$ in $\mathbb Z_N$ is the smallest integer $r$ such that $x^r\equiv 1\text{ mod }N$. If $r$ is even, then $r/2$ is an integer ...
0
votes
1
answer
49
views
Coprimality in a given set of consecutive natural numbers
Given the first n natural numbers, is it possible that every composite odd number is coprime with at least one even composite number and that no two odd numbers share the same even number. For example,...
0
votes
1
answer
35
views
Common elements in finite LCM closed sets.
Let $X$ be a finite set of square-free integers. Suppose that whenever $a, b \in X$, we have $lcm(a, b) \in X$. Does it follow that there exists $x \in X$ that divides at least half of elements of $X$?...
-1
votes
1
answer
143
views
How many shared numbers between all factors of 465 and all multiples of 3 between 20 and 100?
I'm trying to understand this GMAT question.
I've tried looking at the following questions (Determine the Number of Multiples of Given Numbers $\le$ 1000 and How many multiples of 3 are between 10 ...
0
votes
1
answer
93
views
Under what conditions on $p$ and $q$, the integers $a$ and $b$ have a common prime divisor
Let us consider a formula of the form:
$$a=(p/q)b$$
where $a, p,q,b$ are positive integers such that $p$ and $q$ are coprime.
My question is: Under what conditions on $p$ and $q$ do the integers $a$ ...
1
vote
1
answer
595
views
Estimating the number of integers less than $m$ that are relatively prime to $p_n\#$
Let $m \ge 2$ be an integer.
Let $p_n$ be the $n$th prime so that $p_1 = 2, p_2 = 3,$ etc.
Let $p_n\#$ be the primorial for $p_n$.
Let $\gcd(a,b)$ be the greatest common divisor for $a$ and $b$.
...
2
votes
1
answer
604
views
Condition on prime Factorizations of 2 relatively prime numbers
Let a,b $\in$ Z and let a = p$_1$$^{\alpha_1}$...p$_n$$^{\alpha_n}$ and let b = q$_1$$^{\beta_1}$...q$_n$$^{\beta_n}$. Determine a condition on these two prime factorizations such that gcd(a,b) = 1.
...
0
votes
0
answers
63
views
Question about proof for Euclid's lemma using greatest common divisor
I have been asked to prove the following:
Let p be prime and m,n $\in$ N. If p|mn then p|m or p|n.
My book offers up the following proof:
Assume p divides mn but not m. We need to show that p|n. ...
8
votes
0
answers
447
views
The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$
For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
1
vote
1
answer
292
views
How many numbers $m$ satisfy $1 ≤ m ≤ n$ and $\gcd (m, n) = 1$?
Let $n = p^2 q$ where $p$ and $q$ are distinct prime numbers. How many numbers $m$ satisfy $1 \leq m \leq n$ and $\gcd (m, n) = 1$? Note that $\gcd (m, n)$ is the greatest common divisor of $m$ and $n$...
9
votes
10
answers
13k
views
The lowest number that is a multiple of both 60 and the integer n is 180. Find the smallest possible value of n.
I have one solution but I think it's just a wild guessed one. Tell me if I am correct and also if not, then how should it be done?
What I have done is divided 180 by 60 to get 3. Then take lcm of 60 ...
1
vote
1
answer
2k
views
Common prime divisors of 2 integers
I was trying to solve the task of checking if 2 numbers have same prime divisors. For example 10 has prime divisors of 2 and 5, 50 has prime divisors of 2 and 5, so they have the same prime divisors. ...