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)

-3
votes
2answers
29 views

List the elements of a set [on hold]

Consider the universal set $N$, $$A = \{m: m\ |\ 16\}$$ and $$B = \{n: n \le 16 \text{ and } n \equiv 17 \mod 3\}.$$ List the elements of A, list the elements of B.
0
votes
5answers
68 views

Mathematical induction

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
0
votes
1answer
33 views

Find two numbers, given their greatest common divisor and least common multiple [on hold]

Highest common factor (HCF) of two numbers is $20$. Least common multiple (LCM) of the same two numbers is $420$. Both numbers are higher than $50$. Find the $2$ numbers. I used factorising trees ...
-1
votes
0answers
24 views
2
votes
1answer
37 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
3
votes
1answer
36 views

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$.

Decide if there exist $a$ and $b \in \mathbb{Z}$ such that $a^2=2b^2$. $a,b \neq 0$ We have to solve this kinds of problems using the order of a prime function: $v_p(a) \in \mathbb{Z}$ which tells ...
2
votes
3answers
71 views

$5 \nmid 2^{n}-1$ when $n$ is odd

I want to prove that $$5 \nmid 2^{n}-1$$ where $n$ is odd. I used Fermat's little theorem, which says $2^4 \equiv 1 \pmod 5$, because $n$ is odd then $4 \nmid n$ , so it is done. can you check it ...
6
votes
2answers
81 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
0
votes
3answers
40 views

Find $GCD(n^2+1,n+1)$

$GCD(n^2+1,n+1)$, $n\in \mathbb{N}$ What I did: $n^2+1=(n-1)(n+1) + 0$ So I thought $(n^2+1:n+1)=n+1$ But that doesn't seem to be the case: $n=2$ $n^2+1=5$ $n+1=3$ $GCD(5,3)=1$ Why is the ...
1
vote
2answers
12 views

Prove the order of the group homomorphism of an element divides the order of the element.

Let $\phi : G \rightarrow H$ be a group homomorphism. Prove $\forall g \in G$, the order of $\phi(g)$ divides $g$. I've gotten to the point where I've shown that if, $ord(\phi(g)) < ord(g)$ then ...
1
vote
2answers
48 views

For a primitive Pythagorean triple $(a, b, c)$, is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?

Let $(a, b, c)$ be a primitive Pythagorean triple. I know that $\gcd(a,b,c) = 1$. Is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?
0
votes
3answers
27 views

Binary remainder not equal to the decimal remainder

I am having a weird result. I am dividing the binary number $10101010100000$ by $10011$. In binary division. I get $R= 0100$ which is 4. However, If I consider the decimal representation of the ...
-3
votes
1answer
40 views

can a positive integer have 2010 facters? [closed]

For any positive integer 𝑛, let 𝑓(𝑛) be the number of distinct positive integer factors of 𝑛 including 1 and n. Which of the following is (are) true? I There is a positive integer 𝑛0 such that ...
3
votes
3answers
57 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
1
vote
2answers
89 views

how $1/0.5$ is equal to $2$?

My question is how $1/0.5$ is equal to $2$. I am not asking the mathematical justification that $1/0.5=10/5=2$. I know all this. I just want to know how it is two... a lay man justification. ...
2
votes
1answer
38 views

How to show that $\mathbb Z+x \mathbb Q[x]$ is a GCD domain ?

How to show that $\mathbb Z+x \mathbb Q[x]$ is a Bezout domain , that is sum of two principal ideals is again a principal ideal ? Or at least , how to show that it is a GCD domain ? ( This will then ...
1
vote
1answer
33 views

Looking for an example of a GCD domain which is not UFD

I know that every UFD (unique factorization domain ) is a GCD domain i.e. g.c.d. of any two elements , not both zero , exists in the domain . I am looking for an example of a GCD domain which is not ...
2
votes
0answers
28 views

Polynomials and Divisibility Rule.

The question is this - If $f(x)$ and $g(x)$ are two polynomials such that the polynomial $h(x)=xf(x^3)+x^2g(x^6)$ is divisible by $x^2+x+1$, then which of the following are true? 1. $f(1)=g(1)$ ...
-1
votes
0answers
14 views

HCF by Division method of Polynomials [closed]

Find step by step Highest Common Factor(HCF) by division method of these two polynomials i.e 2X^3-5X^2+4 and X^3-16X+24.
1
vote
1answer
30 views

Finding a natural number $k>1$ such that $k$ divides $(26+35n)$ and $(3+7n)$

I am trying to find a natural number $k>1$ such that $k$ divides $(26+35n)$ and $k$ divides $(3+7n)$ for some integer $n$. I know that $(ka)=(26+35n)$ for some $a \in Z$ and $(kb)=(3+7n)$ for some ...
2
votes
0answers
21 views

Show that $\gcd(x_1,…,x_k,x_{k+1})=\gcd(\gcd(x_1,…,x_k),x_{k+1})$

I would really appreciate if you could check my proof. Thank you. Show that $\gcd(x_1,...,x_k,x_{k+1})=\gcd(\gcd(x_1,...,x_k),x_{k+1})$ Let $\gcd(x_1,...,x_k,x_{k+1})=a$. We first show that $a$ ...
1
vote
4answers
76 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
0
votes
1answer
42 views

If $m\mid n$ then $p^m-1\mid p^n-1$ [duplicate]

I know $m$ ,$n$ are two positive integer numbers such that $m\mid n$. If $p$ is a prime number, I want to show $p^m-1\mid p^n-1$.
0
votes
3answers
31 views

How to formally prove: if $d\mid da+b$, then $d\mid b$?

How would I formally prove that for the integers $a$, $b$, and $d$, if $d\mid da+b$, then $d\mid b$? Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty ...
0
votes
1answer
18 views

Divisibility in a certain ring and divisibility in integers.

Divisibility in the ring $\mathbb{Z}[x,y]$ implies divisibility in $\mathbb{Z}$ ? Let $P(x,y)=Q(x,y)\cdot R(x,y)$ with $P,Q,R$ polynomials with integer coefficients, evaluating in $(x,y)=(a,b)$ with ...
1
vote
3answers
34 views

Proving gcd($a,b$)lcm($a,b$) = $|ab|$

I was trying to prove that $$ dm = |ab|$$ where $d$ = gcd(a,b) and m = lcm(a,b). So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. ...
0
votes
2answers
40 views

Find $a,b,c$ if $\gcd(a,b,c)=10$ and $\text{lcm}(a,b,c)=100$ [closed]

Find all natural numbers $a,b,c$, so that $\gcd(a,b,c)=10$ and $\text{lcm}(a,b,c)=100$. Any ideas how to approach this problem?
5
votes
0answers
38 views

Generalisation of $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b)$ to $\gcd\left(\frac{a^n-b^n}{a-b},a^m-b^m\right)$?

We have the identity $$\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n\gcd(a,b)^{n-1},a-b).$$ (see here) This appears to be a quite useful result with various applications. I wonder whether there is ...
2
votes
4answers
72 views

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $ 7\mid b$

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $7\mid b$ What I did: I found the possible remainders for $a^2$ are $0, 1, 2$ and $4$. I think I should say $r_7(a^2)+r_7(b^2)$ can't equal any ...
1
vote
0answers
25 views

$\max{a_1}$ in $(x_n)_{n\in\mathbb{N}}$

Let be $x_1,x_2,x_3,\ldots,$ a sequence of positive integers. Suposse the folowing conditions are true for all $n\in\mathbb{N}$ $n|x_n$ $|x_n-x_{n+1}|\leq 4$ Find the maximun value of $x_1$ I ...
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^+} ...
0
votes
0answers
32 views

On odd perfect numbers $N$ given in the Eulerian form $N = {q^k}{n^2}$, Part II

(Note: This has been cross-posted to MO.) A positive integer $N$ is said to be perfect if $\sigma(N) = 2N$, where $\sigma(x)$ is the sum of the divisors of $x$. An odd perfect number $N$ is said to ...
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 ...
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) ...
-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
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
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$ = ...
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
33 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. ...
5
votes
8answers
284 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
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
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 ...
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
0answers
36 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)$ ...