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

learn more… | top users | synonyms

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
598 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
42 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 ...
-4
votes
3answers
66 views

Is $ n^{2} + 1 $ divisible by $ 7 $? By $ 13 $? [closed]

1) Does there exist a positive integer $ n $ such that $ n^{2} + 1 $ is divisible by $ 7 $? Prove assertions. 2) Does there exist a positive integer $ n $ such that $ n^{2} + 1 $ is divisible by $ 13 ...
13
votes
0answers
328 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
55 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
32 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
58 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
111 views
2
votes
3answers
72 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?
-3
votes
2answers
74 views

If 3 is the least prime factor of number ‘a' and 7 is the least prime factor of number ‘b'.Least prime factor of a+b is [closed]

If 3 is the least prime factor of number ‘a' and 7 is the least prime factor of number ‘b'. Then what is the Least prime factor of a+b?
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 ...
-2
votes
1answer
71 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
678 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
804 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
55 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
40 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 ...
3
votes
5answers
267 views

What does “$x$ divides $y$” mean?

I need to negate the following sentence: "If for the integers $x, y, z$ we know that $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$." In this scenario, what does it mean for $x$ to ...
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
181 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
45 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
116 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
80 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
127 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 ^ ...
1
vote
1answer
24 views

Is it possible to compute $\sigma(AB)$ if $\gcd(A, B) = C > 1$?

Let $\sigma$ be the classical sum-of-divisors function. I know, for one, that $\sigma$ is weakly multiplicative (that is, $\sigma(xy) = \sigma(x)\sigma(y)$ whenever $\gcd(x, y) = 1$). Well, of ...
1
vote
1answer
31 views

A question about $\gcd$ and divisibility

Let $\sigma$ be the classical sum-of-divisors function. Suppose that I have the following equations: $$2n^2 - \sigma(n^2) = \frac{\sigma(n^2)}{q^k}\cdot{\sigma(q^{k-1})}$$ $$2n^2 - \sigma(n^2) = ...
3
votes
1answer
29 views

What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$?

Let $\sigma$ denote the classical sum-of-divisors function. What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$? Update: I have transferred the transcript of my attempt to an actual answer to this MSE ...
0
votes
2answers
54 views

Is there a solution to this system of equations?

Is there an integer solution to this system of equations? $$\gcd(x, \sigma(x)) = 2x - \sigma(x) = \frac{x}{3} = \frac{\sigma(x)}{5}$$
0
votes
1answer
56 views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...
6
votes
4answers
97 views

Divisibility of polynomials in a subfield of a field.

I am trying to prove the following assertion: Let $K\subset L$ be fields, let $f,g\in K[x]$ be such that $f\mid g $ in $L[x]$, then $f\mid g$ in $K[x]$. We clearly have that $fh=g$ for some ...
1
vote
3answers
246 views

Why does Wolfram Alpha say that $n/0$ is complex infinity?

I typed a number divided by 0 on Wolfram Alpha and thought that it would say "undefined". However, when I pressed enter it told me that the answer is complex infinity. I have always been taught ...
0
votes
0answers
29 views

When is ${(1-t^2)^{-N/2}}{\det(f_t(A))}$ expressible as polynomial?

Given a matrix valued function $f_t:\mathbb R^{N\times N} \mapsto \mathbb R^{N\times N}$. For $f_t(A)=B$ both $A$ and $B$ are symmetric. Which properties can be assigned to $f_t$, when the following ...