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)

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
35 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
34 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
54 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
89 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$ = ...
0
votes
1answer
60 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
47 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
7answers
320 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
25 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
53 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
45 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
41 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 ...
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
78 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
53 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
83 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
28 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
57 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
64 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 ...
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 ...
2
votes
0answers
86 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
1answer
42 views

Quotient and Remainder of Numbers

May I ask what is the logic behind the quotient and remainder for numbers in such situation. ...
2
votes
1answer
73 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 ...
1
vote
1answer
34 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 ...
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 ...
4
votes
5answers
88 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.
-5
votes
1answer
65 views

Division by zero after removing factor. [duplicate]

I know that anything divided by zero is undefined and I understand why. However, I have just discovered this sum, and it confused me greatly. Could anyone explain what is going on here: $$x-x=0$$ ...
1
vote
3answers
31 views

If $x,y$ are integers greater than $1$ and $n$ is a positive integer such that $2^n + 1=xy$ , $\exists 1< a<n$ such that $2^a|x-1$ or $2^a|y-1$?

If $x,y$ are integers greater than $1$ and $n$ is a positive integer such that $2^n + 1=xy$ , then is it true that either $2^n|x-1$ or $2^n|y-1$ ? I have only been able to observe that both $x,y$ are ...
0
votes
1answer
31 views

Simple number theory

I'm new in number theory and I was asked this question: For the number $N$ output the amount of numbers $M$, such that $1 \le M \le N$, $\gcd(M, N) \ne 1$ and $\gcd(M, N) \ne M$. How can i solve it?
2
votes
2answers
70 views

Find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm.

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm. Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer. ...
0
votes
1answer
44 views

Show that if $p\mid m^2$ then $p \mid m$ and hence $p^2 \mid m^2$

Show that if $p\mid m^2$ then $p \mid m$ and hence $p^2 \mid m^2$ I don't understand what is being asked of me. I thought this question was asking if $p$ divides $m^2$, then $p$ divides $m$, and ...
2
votes
2answers
85 views

Divisibility of sum of two numbers by $24$.

Let $m$ and $n$ be natural numbers such that $(mn + 1)$ is divisible by $24$. Then $m + n$ is divisible by: $2$ $3$ $8$ $12$ $24$ All of the above The answer given is 6. (all of the above). ...
4
votes
1answer
44 views

Prove that $2^{4n}+1$ cannot be a prime if $3|n$

$2^{4n}+1$ cannot be a prime if $3|n$ and $n>0$ My Try: $$2^{12k}+1\equiv (-1)^{3k}+1 \equiv0\pmod{17}$$ So it divisible by $17$ for odd $k$. But how to complete the proof?
0
votes
1answer
36 views

Polynomial long division modulo 7,

I need to determine the quotient and remainder using polynomial long division in $Z_7[x]$. I'm not sure how to tackle it with the polynomials given, and I'm growing frustrated by it. I need to divide ...
12
votes
3answers
343 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
1answer
40 views

Prove that $[(a|b)\land(c|d)]\Longrightarrow ac|bd;\, a|b\Longrightarrow ac|bc;\, ac|bc\Longrightarrow a|b.$

Prove that: $$(a): [(a|b)\land(c|d)]\Longrightarrow ac|bd;$$ $$(b): a|b\Longrightarrow ac|bc;$$ $$(c): ac|bc\Longrightarrow a|b.$$ Proof: (a) By definition of divisibility, ...
8
votes
4answers
121 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...
0
votes
1answer
27 views

Trivial and nontrivial GCD of polynomials

What is the difference between trivial and non-trivial GCDs of two polynomials: $f,g$ where $f,g \in Q[x]$? I know if $f,g \in Z[x]$, the only non-trivial GCD is 1, and everything else is trivial. ...
0
votes
1answer
46 views

Is there a way to prove that 2y(y-1) is divisible by four other than by means of induction?

I am going trough some of my older textbooks and in one problem you have to prove that 2y(y-1) is divisible by four if y is a whole number. Its trivial to prove this by using induction, but this ...