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
1answer
37 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
75 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
123 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
42 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
17 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
55 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
28 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
3answers
58 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
151 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
55 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, the 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
55 views

Looking for an example of a GCD domain which is not a 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 ...
3
votes
1answer
50 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
vote
1answer
31 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
4answers
87 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
45 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
32 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
23 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 ...
2
votes
3answers
50 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$. ...
5
votes
0answers
43 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 ...
4
votes
4answers
206 views

Odd divisibility induction proof

Prove that for odd $n>3$ $$64\ | \ n^4-18n^2+17$$ I checked that for $n=5$ it works. I think I need to assume that for $2n+1$ it holds and show that $2n+3$ also holds. Any ideas?
2
votes
4answers
73 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 ...
0
votes
0answers
37 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
37 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
35 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 ...
3
votes
2answers
72 views

Why is the sum of the digits in a multiple of 9 also a multiple of 9?

The sum of the digits in $9 k$ (where $k$ is an integer) is a multiple of $9$: for example $$9\cdot 1=9$$ $$9\cdot 7=63 \qquad \text{and } 6+3=9\cdot 1$$ $$9\cdot 11=99 \qquad \text{and } ...
2
votes
2answers
55 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
91 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
46 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$ = ...
1
vote
1answer
63 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
72 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. ...
6
votes
8answers
341 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
34 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
27 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
59 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
48 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
37 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
47 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
67 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
31 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 ...
3
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
79 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 ...
0
votes
3answers
57 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
84 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
1answer
30 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 ...
0
votes
0answers
63 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
69 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 ...