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

learn more… | top users | synonyms

4
votes
1answer
49 views

Smallest $a$ such that both $a$ and $a+5$ and $a$ and $a+7$ have a common factor

Which is the smallest integer number $a$ so that the highest common factor of $a$ and $a+5$ is not $1$ and the highest common factor of $a$ and $a+7$ is not $1$ either? I think that it is $35$. Am I ...
4
votes
5answers
395 views

What is easiest way to know it the large number divisible by 57

What is the easiest way to know if large number is divisible by 57? For example, how could I deduce that 57 divides 300000177?
0
votes
0answers
28 views

Divisibiltiy of the order of elements in a group

Let $G$ be a finite group and ket $y \in G$. How many elements $x \in G$ are there such that the order of $y$ is divisible by the order of $x$
2
votes
2answers
48 views

If $a\mid b+c$ and $\gcd(b,c)=1$, prove $\gcd(a,b)=\gcd(a,c)=1$

I have the following: $b+c=av$ for some integer $v$, and $a=dm$ and $b=dn$ for $d=\gcd(a,b)$ and some integers $m,n$. Then, $c=av-b=dmv-dn=d(mv-n)$. So, $d|c$, and we know that $d|a$ and $d|b$. I ...
3
votes
1answer
44 views

Prove that for any positive integer $n$ the number $1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$ is divisible by $2^{n-1}$.

Let $a=4k-1$, where $k \in \mathbb{Z}$. Prove that for any positive integer $n$ the number $$1 - {n \choose 2}a + {n \choose 4}a^2 - {n \choose 6}a^3+\cdots$$ is divisible by $2^{n-1}$. My ...
2
votes
0answers
34 views

Finding solutions to a symmetric divisibility condition $x\mid p(y),\;y\mid p(x)$

In general, are there strategies for finding all integers $x$ and $y$ such that $x \mid p(y)$ and $y \mid p(x)$ for some polynomial $p$ with integer coefficients? For example, could we find all ...
3
votes
2answers
52 views

A question on greatest common divisor

I had this question in the Maths Olympiad today. I couldn't solve the part of the greatest common divisor. Please help me understand how to solve it. The question was this: Let $P(x)=x^3+ax^2+b$ and ...
3
votes
2answers
67 views

Does $p^n$ divide $\binom{p^{n+m-1}}{m}$?

Let $n, m \in \mathbf N$ and $p$ an odd prime number. Then does $p^n$ divide $\binom{p^{n+m-1}}{m}$ ? It seems true, but I can not find a clue. Can I have any hint?
4
votes
10answers
294 views

Why does the largest $x$ such that $a$, $b$ divided by $x$ leave the same remainder equal $a-b$?

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$. It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I ...
1
vote
5answers
129 views

Show that $30 \mid (n^9 - n)$

I am trying to show that $30 \mid (n^9 - n)$. I thought about using induction but I'm stuck at the induction step. Base Case: $n = 1 \implies 1^ 9 - 1 = 0$ and $30 \mid 0$. Induction Step: Assuming ...
1
vote
5answers
350 views

For every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$

I'm trying to prove that for every integer $n$, $15\mid n$ iff $3\mid n$ and $5\mid n$. The first part of this bi-conditional was easy for me to prove, but I'm having problems with the second. Here is ...
6
votes
3answers
1k views

Prove that every positive integer $n$ is a unique product of a square and a squarefree number

I am trying to prove that for every integer $n \ge 1$, there exists uniquely determined $a > 0$ and $b > 0$ such that $n = a^2 b$, where $b$ is squarefree. I am trying to prove this using the ...
1
vote
0answers
31 views

Number of binomial coefficients , ${ n \choose k}$ k $\in$ [0,n] , that are divisible by a prime p?

For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n ...
7
votes
3answers
616 views

Proof of Wolstenholme's theorem

According to the theorem, if $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{p-1} =\frac{r}{q}$$ then we have to prove that $r\equiv0 \pmod{p^2}$. (Given $p>3$, otherwise ...
1
vote
0answers
43 views

using Fibonacci numbers prove that if $d|n$ then $F_d|F_n$ [duplicate]

The first question was to prove that $\gcd(F_{n+1},F_n) = 1$ So i tried to use it but with no success. any help or clue will appreciated thanks
3
votes
2answers
96 views

Which prime divides $18^{29}+1$? [closed]

I am struggling with the following problem. Any help will be appreciated. let $n= 18^{29}+1$. Prove that $n$ is divisible by $19$. Prove that if $ p $ is a prime which divides $n$, $p\ne19$,then $p ...
1
vote
1answer
55 views

When does $c\mid a(n+x)+b+1$, if we know that $c\mid an+b$?

If $an+b$ is divisible by $c$. Then for which values of $x$ will $a(n+x)+b+1$ be divisible by $c$? $a$, $b$, $c$, $n$, $x$ are all non-negative integers.
4
votes
2answers
63 views

Divisibility of numbers

Find all positive integers $x,y$ such that $2x+7y$ divides $7x+2y$. I somehow managed to show that $x$ is greater than $y$. But couldn't proceed further.
2
votes
1answer
20 views

Tools for dealing with a divisibility problem with powers of 2 and 3?

I'm trying to solve an equation with congruences: $$ \sum_{i=1}^{N}2^{\sum_{j=1}^{i} n_j}3^{N-i} \equiv 0 \; (\text{mod} \; 2^{\sum_{j=1}^{N}}-3^N) $$ The unpacked version (assuming ...
0
votes
0answers
19 views

If :$\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ how i deduce the remain of :$\sum_{k=1}^{n}k^{-p}$?

I have tried to determine the remain of this serie:$\sum_{k=1}^{n}k^p$ : I got this formula $\sum_{k=1}^{n}k^p =(\frac{n(n+1)}{2})\mod(p)$ ,where $p$ is prime and $k$ is positive integer .Now ...
13
votes
0answers
364 views

My first proof that uses the well-ordering principle (very simple number theory). Please mark/grade.

What do you think about my first proof that uses the well-ordering principle? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof ...
3
votes
2answers
56 views

First contest problem

I downloaded a contest and worked the first problem which is: There exists a digit Y such that, for any digit X, the seven-digit number 1 2 3 X 5 Y 7 is not a multiple of 11. Compute Y. My ...
-2
votes
6answers
1k views

The sequence of integers which are not divisible by 3 [closed]

Is there a known formula to generate the sequence of all integers which are not divisible by 3? Additionally, is there a formula to generate the sequence of all integers that are not divisible by 3 ...
0
votes
2answers
33 views

Induction proof, divisibility

I'm struggling with an induction problem here. I have to prove that $2^{2^n}- 6$ (two to the power of two to the power of $n$ minus six) is divisible by $10$. I already figured some steps and I ...
0
votes
1answer
53 views

Divisibility: if $a \mid b$ and $b \mid c$, then $a \mid (b+c)$

So I'm unsure as to how to prove this: If $a \mid b$ and $b \mid c$, then $a \mid (b+c)$. I'm aware of the divisibility properties such as: if $a \mid b$, then $b=ak$ for some integer $k$. I ...
2
votes
1answer
64 views

Find all positive integers solutions such that $3^k$ divides $2^n-1$

How can I find all positive of $k$ and $n$ such that $$\frac {2^n-1}{3^k}$$ is an integer? I know that $$2^n-1\equiv 0\pmod 3$$ If $n=2p$ with $p$ integer , $$2^n-1\equiv 0\pmod 9$$ If $n=6p$, ...
2
votes
0answers
58 views

Proof relating to Euclidean Algorithm

The question is as follows: (1): Let m and n be positive integers with n < m and let r be the remainder when m is divided by n. Prove that $$r < \frac m2$$ (2): The Euclidean Algorithm for ...
0
votes
2answers
147 views
2
votes
3answers
73 views

Prove that if $n^{2} - \left(n - 2\right)^{2}$ is not divisible by $8$ then $n$ is even

Let $n$ be an integer. Prove that if $n^{2} -\left(n - 2\right)^{2}$ is not divisible by $8$ then $n$ is even. Can anyone help me step by step to understand this?
4
votes
4answers
98 views

Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction

How should I go about solving a problem like this using induction? Would I: First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$. Then assume $(n = k)$ so that you have $6^{2(k) + 1} ...
0
votes
3answers
46 views

Find all $\displaystyle n \in \mathbb{Z}$ such that $\displaystyle k = \frac{1+4n}{5}, \qquad (k \in \mathbb{Z} )$

My question is rather general but I got stuck in that issue after trying to solve a trigonometric equation. After simplifying I got this: $$\sin \left(\frac{5x}{4}\right) + \cos x = 2$$ which is ...
-3
votes
1answer
75 views

Prove that there exist $2015$ consecutive abundant numbers [closed]

A positive integer $N$ is called abundant if the sum of its divisors is greater than $N$: $\delta (N) >N$. My question is: Prove that there exists an integer: $k\in\mathbb N\setminus\{0\}$ ...
90
votes
8answers
12k views

Are half of all numbers odd?

Plato puts the following words in Socrates' mouth in the Phaedo dialogue: I mean, for instance, the number three, and there are many other examples. Take the case of three; do you not think it may ...
12
votes
6answers
682 views

Is 1100 a valid state for this machine?

A room starts out empty. Every hour, either 2 people enter or 4 people leave. In exactly a year, can there be exactly 1100 people in the room? I think there can be because 1100 is even, but how do I ...
1
vote
1answer
59 views

Sum of $m\leq 300$ such that if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$

Find the sum of all the integers $m$ with $1≤m≤300$ such that for any integer $n$ with $n≥2$, if $2013m$ divides $n^{n}-1$, then $2013m$ also divides $n-1$. Unfortunately I cannot think of ...
5
votes
5answers
835 views

Divisibility by 7

What is the fastest known way for testing divisibility by 7? Of course I can write the decimal expansion of a number and calculate it modulo 7, but that doesn't give a nice pattern to memorize because ...
3
votes
4answers
56 views

Prove that if $p$ is prime greater than $3$ ,then: $p^2+2015$ is multiple of $24$?

Prove that if $ p $ is prime number $(p >3)$, then the number $p^2+2015$ is multiple of $24 $? Thank you for any help
2
votes
1answer
44 views

Find the greatest positive integer $x$ such that $23^{6+x}$ divides $2000!$

I'm currently reading Andreescu and Andrica's Number Theory: Structures, examples and problems. Problem 1.1.7 states : Find the greatest positive integer $x$ such that $23^{6+x}$ divides $2000!$. The ...
2
votes
2answers
64 views

How to prove that $(p-1)^2$ $\mid$ $(p-1)!$ when $p$ is a prime number and $p>5$?

I say that $p-1$ $\mid$ $(p-1)!$ then I want to prove that $p-1$ $\mid$ $(p-2)!$. I started by saying that $p-1$ is an even number so $2\mid (p-1)$ and that means that $\frac{p-1}{2}$ is an integer. ...
5
votes
4answers
2k views

Proof By Induction Divisibility Question: $12\mid 3^n + 7^{n-1} + 8$

Prove that $3^n + 7^{n-1} + 8$ is divisible by $12$ for all positive integers $n$. I have proved it is true for $n=1$ and I have done the 'assume $n=k$' step, but after getting $3^{k+1} + 7^k + 8$, I ...
0
votes
3answers
186 views

Euclidean algorithm for $\gcd(60,17)$

Hay I am going over some old exams and hit this: (a) Use the Euclidean algorithm to show that $\gcd(60; 17) = 1$. (b) Hence find integers $x, y$ satisfying $60x + 17y = 1$. (c) Find ...
3
votes
4answers
48 views

$\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$?

If $\gcd(N, a)=1$, then we have $\gcd(N, N-a)=1$. More generally, can we have $\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$? Thanks in advance.
3
votes
8answers
118 views

Proving that $12^n + 2(5^{n-1})$ is a multiple of 7 for $n\geq 1$ by induction

Prove by induction that $12^n + 2(5^{n-1})$ is a multiple of $7$. Here's where I am right now: Assume $n= k $ is correct: $$12^k+2(5^{k-1}) = 7k.$$ Let $n= k+1 $: $$12^{k+1} + 2(5^k)$$ ...
6
votes
6answers
143 views

How to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction?

I want to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction. My first step is replace $n$ with $1$. $2^{1+2}+3^{2(1)+1}$ $2^3+3^3$ $8+27$ $35 = 7\times 5$ The next step is assume ...
3
votes
4answers
89 views

Number of fingers of a Martian

I have a question about what seems to be modular arithmetic, but I can't quite get the answer. The problem goes along the lines of: It is often said Earthlings use the decimal system because they ...
4
votes
0answers
67 views

$d$ and $d+1$ both dividing certain integers

\begin{align} & 1\cdot 72 \\ & 2\cdot 36 \\ & 3\cdot 24 \\ & 4\cdot 18 \\ & 6\cdot 12 \\ & 8\cdot 9 \end{align} When the divisors of a number are listed in this way, let us ...
1
vote
0answers
36 views

Bezout Coefficient for polynomials in sage?

I want to find the bezout coefficient for those 2 polynomials : $f = 1+x-x^2-x^4+x^5$ and $g = -1+x^2+x^3-x^6$ when I use the gcd function in sage the output is : ...
0
votes
1answer
43 views

Are Zero Degree polynomials Considered monics?

DO zero degree polynomials that is constant polynomials considered monic polynomials? Example F(x)=16 Does it Matter the Field or the Integral region where i take the coeficients from?Sorry if the ...
6
votes
2answers
130 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&=& ...
11
votes
2answers
2k views

$\gcd(b^x - 1, b^y - 1, b^ z- 1,…) = b^{\gcd(x, y, z,…)} -1$ [duplicate]

Possible Duplicate: Number theory proving question? Dear friends, Since $b$, $x$, $y$, $z$, $\ldots$ are integers greater than 1, how can we prove that $$ \gcd (b ^ x - 1, b ^ y - 1, b ^ ...