This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms (1)

0
votes
0answers
32 views

Existence of non-coprime between an integer and an arithmetic sequence

Take two relatively prime numbers $m,n \in \mathbb{Z}$ (i.e. $gcd(m,n) = 1$) where $m \neq 1$. Show that: $$\forall a \in \mathbb{Z} \textrm{ s.t. } 0<a<n$$ $$\exists i \in \mathbb{Z^+} ...
1
vote
2answers
34 views

A question related to the concept of being “relatively prime”

Suppose that I have $a, b, c, d \in \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers. If I have the equation $ab = 2cd$ and I know that $\gcd(a,c)=\gcd(c,d)=1$, then it follows that I ...
1
vote
5answers
212 views

Show {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$}

I have the following problem: Let $a, b \in\mathbb{Z}$. Show that {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$} I understand that the Bezout's lemma says that $gcd(a,b) = ...
6
votes
5answers
4k views

Prove $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ if $\gcd(a,b) = 1$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) > = 1$ or $\gcd(a+b, a-b) = 2$ holds. I think the first step should look something like this: $d = \gcd(a+b, a-b) ...
-1
votes
0answers
50 views

Prove that $\{ ax+by\mid x,y\in\mathbb Z\} = \{ n(a,b) \mid n\in\mathbb Z\}$ [duplicate]

Prove the following proposition: Suppose $a,b$ are fixed integers. Then $\{ ax+by\mid x,y\in\mathbb Z\} = \{ n(a,b) \mid n\in\mathbb Z\}$.
2
votes
2answers
52 views

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ?

If $n$ is a positive integer such that $2^n+n^2$ is a prime number , then is it true that $6|n-3$ ? Trivially $n$ cannot be even , so this leaves us only with the possibilities $n \equiv1,3,5( \mod 6) ...
2
votes
3answers
60 views

Number Theory Simple Proof Confusion

Suppose that c|ab and (b, c) = 1. Then c|a Proof (ab, ac) =|a|(b, c) = |a|. But by hypothesis, one has c|ab, which implies that c|(ab, ac). We thus conclude that c|a. And the proof is complete. I am ...
2
votes
2answers
86 views

Proving $2^{2^n}+3^{2^n}+5^{2^n}$ is divisible by $19$ for all $n\geq 1$ by induction

I came across the following in the book Handbook of Mathematical Induction: $$ 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+}\tag{1} $$ Apparently, this problem is not so bad if you think ...
2
votes
1answer
23 views

Number of bounded divisors of an integer

Given integers $n,t$, what is an upper bound for the number of integers dividing $n$ in the interval $\{1,\ldots,t\}$? When $t=n$ this boils down to the classical divisor bound ...
0
votes
2answers
81 views

If a prime $p\mid b$ and $a^2=b^3$, then $p^3\mid a$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...
0
votes
2answers
59 views

If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$

Suppose that $k$, $n$, and $d$ are integers and $d$ is not $0$. Prove: If $d$ divides $k$ and $d$ divides $n$, then $d$ divides $(8k - 3n)$. You may not use the theorem stating the following: Let ...
12
votes
3answers
328 views

Mental Primality Testing

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?" Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is ...
2
votes
0answers
28 views

$m+n = (n,m)^2; n+l = (n,l)^2; l+m = (m,l)^2$

Find all natural numbers $m,n,l$ such that $$m+n = (n,m)^2; \quad n+l = (n,l)^2; \quad l+m = (m,l)^2$$ where $(a,b)$ is the greatest common divisor of $a$ and $b$. I only managed to find that if ...
1
vote
2answers
36 views

Proof that $(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ [duplicate]

$(2^m - 1, 2^n - 1) = 2^d - 1$ where $d = (m,n)$ my work: I assumed m = da , n = db for a,b $\in$ Z. Now, $2^m - 1$ = $2^{da} - 1$ = $(2^d)^a - 1$ = $x^a - 1$ where $x = 2^d$. similarly $2^n - 1$ = ...
3
votes
5answers
120 views

How can I show that $\phi(m) \mid \phi(n)$? [duplicate]

I want to prove that: $$\text{ if } m,n \geq 1 \text{ and } m \mid n,\text{ then } \phi(m) \mid \phi(n).$$ How can I show this? I thought the following: $$m \mid n \Rightarrow \exists k \in ...
2
votes
2answers
125 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
0
votes
1answer
59 views

Greatest integer which divides $2001\times\ 2002\times 2003\times\ \cdots\times\ 2009$

Here i have a problem. Find the greatest integer which divides $2001\times\ 2002\times 2003\times\ \cdots\times\ 2009$. I couldn't get the problem actually, how to start with?
1
vote
3answers
34 views

Determining maximum possible number of pieces of a bar with given number of cuts

I came across a challenge on Hackerrank which has me stumped literally. It is a coding problem but I am not looking for the code, rather I can't figure out the mathematical approach towards it. ...
0
votes
2answers
272 views

Long division: 24158 divided 6

Long division has always been a weakness of mine and some how I've gotten through school and sixth form without it, but i'd like to learn it, it's just that I have a problem with intuition. So I know ...
6
votes
2answers
52 views

The product of all differences of the possible couples of six given positive integers is divisible by 960.

How can I show that the the product of all differences of the possible couples of six given positive integers is divisible by $960$? $$x_1≥x_2≥x_3≥x_4≥x_5≥x_6$$ $$960\mid (x_1-x_2 )(x_1-x_3 ...
0
votes
1answer
33 views

Suppose $m,n$ are positive integers such that $a-b|a^m-b^n , \forall a,b \in \mathbb Z , a-b \ne0$ , then is it true that $m=n$?

Suppose $m,n$ are positive integers such that for all $a\neq b$ one has $a-b\mid a^m-b^n$, then is it true that $m=n$ ?
2
votes
1answer
67 views

On Descartes numbers

This question is an offshoot of this earlier MSE post. Citing Banks, et. al.: "Let us call an integer $n$ a Descartes number if $n$ is odd, and if $n = km$ for two integers $k, m > 1$ such that ...
0
votes
0answers
105 views

Automata to detect numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automata such that it can detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ ...
0
votes
0answers
37 views

How does the factor command on the TI-89 works?

So to put my question in context, I am working on the following problem. Let $N=1291233941$. Eve's magic box tells her the following three encryption/decryption pairs for $N$: $$(1103927639, ...
0
votes
2answers
36 views

Prove $n!\mid\prod_{k=i}^{i+n-1}k$

I have no idea how to prove this, I haven't yet learned much about this kind of product. $$ n!\mid\prod_{k=i}^{i+n-1}k $$
0
votes
3answers
29 views

Prove that gcd(e,f)=1

could someone please help me with this proof? Suppose that a, b ∈ N, and d = gcd(a, b). Since d divides a, we have a = de for some integer e, and similarly b = df for some integer f. Prove that ...
2
votes
4answers
66 views

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction

Prove $24\mid5^{2n}+12n^2-36n-1$ using induction What I thought: Inductive hipothesis: $$ 5^{2n}+12n^2-36n-1=24k $$ Inductive step: $$ 5^{2(n+1)}+12(n+1)^2-36(n+1)-1=24q $$ $k,q \in \mathbb{Z}$ ...
1
vote
1answer
30 views

divisible large degree polynomial

Let $n$ be an even positive integer and $a$, $b$ real numbers such that $b^n=3a+1$. Prove that if $(X^2+X+1)^n-X^n-a$ is divisible by $X^3+X^2+X+b$, then $a=0$ and $b=1$. I am thinking of using the ...
2
votes
4answers
53 views

Find every n $\in \mathbb{N}$ such that $n+1 \mid n^2+3$

Find every n $\in \mathbb{N}$ such that $n+1 \mid n^2+3$ What I did: $n+1 \mid n^2+3$ and $n+1 \mid (n+1)^2=n^2+2n+1$ So $n+1 \mid (n^2+3)-(n^2+2n+1) \Longrightarrow n+1\mid-2(n+1)$ ...
0
votes
2answers
17 views

Let $n,r,a$ be positive integers with g.c.d.$(a,d)=1$ , does there exist integer $m$ relatively prime to $n$ such that $d|m-a$?

Let $n,r,a$ be positive integers with g.c.d.$(a,d)=1$ . Does there exist integer $m$ such that $d|m-a$ and g.c.d.$(m,n)=1$ ?
4
votes
2answers
77 views

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. [duplicate]

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. $1990 = 2 \times 5 \times 199$. Now $a \equiv 0 \pmod {2}$, $a \equiv 4 \pmod{5}$ and $a \equiv 29 \pmod{199}$. Taking first two together we ...
1
vote
1answer
71 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
23
votes
6answers
13k views

If $a^2$ divides $b^2$, then $a$ divides $b$

Let $a$ and $b$ be positive integers. Prove that: If $a^2$ divides $b^2$, then $a$ divides $b$. Context: the lecturer wrote this up in my notes without proving it, but I can't seem to figure out ...
1
vote
3answers
296 views

“Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
0
votes
3answers
50 views

Working out a reverse formula

My math skills are getting rusty. I am trying to work out what the formula should be for calculating price, $P$, based on a formula I used to calculate margin, $\mu$, with a parameter, cost, $C$. ...
9
votes
2answers
82 views

$5^{th}$ power of any integer is of the form $11k$ or $11k +1$ or $11k -1$.

$5^{th}$ power of any integer is of the form $11k$ or $11k +1$ or $11k -1$. Let the integer be $x$. If $x$ has a factor $11$ then $x^5$ is of the form $11k$. Now we consider the case where $11 ...
0
votes
4answers
33 views

Is there a quick parity test for integers expressed with odd radicies?

For integers expressed with an odd base, is there an easy way to tell if the number is odd or even? For an even base, if the ones digit is even, so is the integer. But this doesn't hold true for odd ...
0
votes
1answer
27 views

Solving number divisibility problem using cardinal number of sets!

How many natural numbers $n<10^6$ are divisible by $7$ but not with $10,12$ and $25$? Theorem: Let $n,k\in \mathbb{N}$ and $k\leq n$, then in the set $\{1,2,...,n\}$ we have exactly $\left \lfloor ...
2
votes
0answers
85 views

$(z-k)$ is composite then $(z-1)+(k-1)$ is also composite(A proof for composite number).

Given $z(z-1)$ is divisible by all prime $< n$ where $ n>\sqrt z$ $(z+k)$ is prime. Prove or disprove if $(z-k)$ is composite then $(z-1)+(k-1)$ is also composite. ...
0
votes
0answers
52 views

On odd perfects and spoofs

This question is an offshoot of this MSE post. Let $\sigma$ be the classical sum-of-divisors function. An odd perfect number $N$ is said to be given in Eulerian form if $\sigma(N)=2N$ and ...
5
votes
5answers
62 views

Prove that for $n \gt 6$, there is a number $1 \lt k \lt n/2$ that does not divide $n$

My nine year old asked this question at lunch today: Is there a number that is divisible by everything that is half or less than the number? I immediately answered, "No. I mean, 6. But not for any ...
1
vote
5answers
61 views

Is it possible to split a division problem into parts, like in multiplication?

In multiplication we can mentally split a problem that is too big into multiple problems. For example: 26 * 40 = (20 * 40) + (6 * 40) = 800 + 240 = 1040 This is a very quick way to multiply ...
1
vote
1answer
89 views

Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
0
votes
0answers
23 views

Divisibility of orders on a group

Let $h \in H \leq G$, where $G$ is a finite group and $H$ is a subgroup. From Lagrange's Theorem, we know $o(h)$ divides $|G|$. It is still true for $H$? That is, is $o(h)$ going to divide $|H|$? I ...
0
votes
1answer
39 views

Quotient and Remainder of Numbers

May I ask what is the logic behind the quotient and remainder for numbers in such situation. ...
1
vote
2answers
35 views

Show that if $\gcd(r,s_1) =\gcd(r,s_2) = 1$, then $\gcd(r,s_1s_2) = 1$

Never mind the question. I want to try to solve that on my own. What I want to understand is how this: "Hint. $1 = ar + bs_1,\ 1 = ar + bs_2$" relates to solving it. I'm a little confused by this ...
1
vote
1answer
32 views

For what positive integers is this number-theoretic equation true?

For what odd (positive) integers $x$ is this number-theoretic equation true? $$\gcd(x^2, \sigma(x^2)) = 2x^2 - \sigma(x^2)$$ Here, $\gcd(a, b)$ is the greatest common divisor of $a$ and $b$, and ...
0
votes
3answers
1k views
4
votes
5answers
83 views

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$.

Prove by induction that $n^3 + 11n$ is divisible by $6$ for every positive integer $n$. I've started by letting $P(n) = n^3+11n$ $P(1)=12$ (divisible by 6, so $P(1)$ is true.) Assume $P(k)=k^3+11k$ ...
1
vote
2answers
27 views

Proving divisibility of $a^3 - a$ by $6$

As part of a larger proof, I need to show why $a^3-a$ is always divisible by $6$. I'm having trouble getting started.