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

learn more… | top users | synonyms

3
votes
7answers
89 views

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$

Prove that there are infinitely many integers n such that $4n^2+1$ is divisible by both $13$ and $5$. This can be written as: $$65k = (2n)^2 + 1$$ It's clear that $k$ will always be odd. Now I am ...
2
votes
3answers
162 views

How to prove the number is a prime?

A natural number $n$ has the property that if $d$ divides $n$ then $d+1$ divides $n+1$. Show that $n$ must be a prime.
5
votes
2answers
47 views

If a, b, c are three natural numbers with $\gcd(a,b,c) = 1$ such that $\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$ then show that $a+b$ is a square.

If a, b, c are three natural numbers with $\gcd(a,b,c) = 1$ such that $$\frac{1}{a} + \frac{1}{b}= \frac{1}{c}$$ then show that $a+b$ is a perfect square. This can be simplified to: $$a+b = \frac{ab}...
0
votes
2answers
80 views

Divisibility problem involving the $2015^{th}$ power [closed]

Show that the number $$ (5+2\sqrt6)^{2015} + (5-2\sqrt6)^{2015} - 10$$ is divisible by $960$.
6
votes
5answers
119 views

Prove that the determinant is a multiple of $17$ without developing it

Let, matrix is given as : $$D=\begin{bmatrix} 1 & 1 & 9 \\ 1 & 8 & 7 \\ 1 & 5 & 3\end{bmatrix}$$ Prove that the determinant is a multiple of $17$ without developing it? ...
0
votes
1answer
62 views

Prove that for any prime $p$ there exist natural numbers $a,b$ for which $ p$ divides $a^2+b^2+1$ [closed]

Prove that for each prime $p$ there exist natural numbers $a,b$ for which $p$ divides $a^2+b^2+1$
0
votes
4answers
32 views

Why does dividing a number with $n$ digits by $n$ $9$'s lead to repeated decimals?

For example, $\frac{1563}{9999} = 0.\overline{1563}$. Why does that make sense from the way the number system works? I can vaguely see that since the number $b$ with $n$ $9$'s is always greater ...
1
vote
2answers
65 views

Prove that $7 | (3^{2n + 1} + 2^{n +2})$

Prove that $7 | (3^{2n + 1} + 2^{n +2})$ So far I have: Base case: n = 1 $ = (3^{2(1) + 1} + 2^{(1) +2})$ $ = (3^{3} + 2^{3})$ $ = (35)$ which divides 7 Inductive Step: $ = (3^{2(n +1) + 1} + ...
1
vote
1answer
115 views

How to prove that $a \cdot b$ is not divisible by 5 for $\frac{1}{1} + \frac{1}{2} + … + \frac{1}{99} + \frac{1}{100} = \frac{a}{b}$? [duplicate]

Let $$\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{99} + \frac{1}{100} = \frac{a}{b},$$ where $a,b$ natural numbers and $\gcd(a,b) = 1$. How to prove that $a \times b$ is not divisible by $5$? ...
2
votes
1answer
105 views

Prove that $a^n - b^n$ does not divide $a^n + b^n$ [duplicate]

Prove that $$a^n - b^n \text{ does not divide } a^n + b^n \text { and } a,b,n \in \mathbb{Z}^+. n > 1$$ I have tried to prove this but have had no success. My efforts till now were concerned with ...
2
votes
4answers
34 views

Use the binomial theorem to prove if $m\mid b - a$, then $m \mid b^n - a^n$.

I'm trying to prove that if $m\mid b - a$, then $m \mid b^n - a^n$. I have done it several ways so far, including through induction and through the application of theorems regarding congruence (i.e. ...
0
votes
1answer
20 views

Elementary proof: division by integer makes real number smaller.

It's been so long since I took discrete math, maybe someone here can help me with what ought to be a straight forward and simple proof. Effectively I want to show this: Let a and b be positive ...
0
votes
4answers
121 views

Palindromes on Keypad and divisibility by $111$ [closed]

The integers 1 through 9 are arranged as follows on a rectangular keypad: $\begin{array}{c c c} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{array}$ Consider the 6-digit ...
0
votes
1answer
34 views

Is it possible to know if $X$ is divisible by $Y$ without dividing $X$ by $Y$.

Background I am working on a project involving FPGA's (a configurable logic circuit) and modulus of numbers to determine if $X$ is divisible by $Y$. When I take the modulus of a number a full ...
0
votes
0answers
33 views

Is this correct? Prove n+3 is not divisible by 5 using proof by contradiction

Let $n=5k$, $n$ and $k$ are integers. I will assume $n+3$ is divisible by $5$ which means there is an $m$ such that $n+3=5m$. Now, $n+3-3=5m-3$, i.e. $n=5m-3$. We know that $n$ is divisible by $5$ ...
4
votes
3answers
111 views

$\frac{2abc}{(a+b-c)(b+c-a)(c+a-b)}$ a positive integer

Find all triplets $(a,b,c)$ of positive integers so that $\gcd(a,b,c)=1$ and $$ \frac{2abc}{(a+b-c)(b+c-a)(c+a-b)} $$ is a positive integer. What I've done: first I looked with Mathematica for ...
0
votes
1answer
50 views

Easy way to divide $2^{1000}$ by $59$ [closed]

What will be the remainder when $2^{1000}$ is divided by $59$? What is the easiest way to calculate this?
1
vote
3answers
71 views

Is there a term that is divisible by $67$, in the sequence $10, 110, 1110, 11110, …$

Consider the sequence $10, 110, 1110, 11110, 111110, ...$ Here the $n$ the term $a_n=\sum \limits_{k=1}^n\left(10^k\right)$ Is there a term which is divisible by $67$ ? How can we show that?
5
votes
2answers
78 views

show that $2^k|n\Longleftrightarrow 2^k|a_{n}$

Let sequence $\{a_{n}\}$ such $a_{0}=0,a_{1}=1,a_{n}=2a_{n-1}+a_{n-2}$. show that $$2^k|n\Longleftrightarrow 2^k|a_{n}$$ I try to find the $\{a_{n}\}$ closed form $$a_{n}=\dfrac{(1+\sqrt{2})^n-(1-\...
1
vote
1answer
47 views

Subsets and Divisibility

What is the size of the largest subset, S, of {1,2,...2013} such that no pair of distinct elements of S has a sum divisible by 3? So...I know the very basic divisibility by 3 rule that any number ...
2
votes
6answers
93 views

Prove that $n(n+1)(n+5)$ is a multiple of $6$

I need to prove that $n(n+1)(n+5)$ is divisible by 6. where $n$ is a natural number. I have used the method of induction. But not successful I got the expression $(k^3+6k^2+5k)+3k^2+15k+12$ when $n=k+...
2
votes
2answers
61 views

How do people come up with divisibility tests?

For example, the test for divisibility by $2$ is quite obvious. But I am quite intrigued by the others, particularly $3$, $7$ and $11$. Also I have come across tests for numbers as far as $50$. How do ...
0
votes
4answers
87 views

Prove that if a|bc then a|b or a|c for a, b, c positive integers where a is not zero [closed]

Prove or disprove (by providing a counter-example) that if a|bc then a|b or a|c for a, b, c positive integers where a is not zero.
1
vote
1answer
19 views

Find the remainder and quotient when we will divide $a$ by $q$

When we divide $a$ by $b$ we get remainder $r=10$ and quotient $q=7$ What will be the remainder and quotient when we will divide $a$ by $q$? My attempt: $$a=b\cdot \overbrace{7}^{q}+\overbrace{...
2
votes
1answer
54 views

How to prove that $(p^2)!$ is divisible by $(p!)^{p+1}$?

For each prime $p$, find the greatest natural power of $p!$, which divides the number $(p^2)!$ ($n!=1 \cdot 2 \cdot ...\cdot n$) My work so far: 1) $p=2 \Rightarrow p!=2; (p!)^2=4!=24 \vdots 8=2^3$. ...
0
votes
3answers
39 views

Which is more; even or odd positive factors?

Suppose $f(n)=$ $\{$ ( number of $n$'s positive even factors) $-$ (number of $n$'s positive odd factors) $\}$ How can we prove/disprove the below statement? $f(n)< 0 $ for half or more ...
2
votes
0answers
56 views

Prove or disprove $a^2\mid b^3\Longrightarrow a\mid b$

I need to prove or to give a counter-example: $$a^2\mid b^3\Longrightarrow a\mid b$$ My attempt: First, let's check with small integres,trying to find counter-example: $2^2\mid 6^3\...
2
votes
4answers
100 views

Prove or disprove $d\mid (a^2-1)\Longrightarrow d\mid (a^4-1)$

I need to prove or to give a counter-example: $$d\mid (a^2-1)\Longrightarrow d\mid (a^4-1)$$ My attempt: Yes, this is correct, First: $(a^2-1)=(a-1)(a+1)\\ (a^4-1)=(a-1)(a+1)(a^2+1)$ If $d\...
3
votes
2answers
98 views

Prove that $\gcd(a^2, b^2) = \gcd(a, b)^2$ [duplicate]

The problem's quite clear. Prove that $$\gcd(a^2, b^2) = \gcd(a, b)^2$$ This is easy to understand intuitively and using the Fundamental Theorem of Arithmetic would be easy but I want to prove it by ...
0
votes
2answers
72 views

Can a product of 4 consecutive natural numbers end in 116

So i was given this question with two parts: (a) Prove that the product of two consecutive even numbers is always divisible by 8. (b) Can a product of 4 consecutive natural numbers end in 116? For ...
0
votes
1answer
43 views

The primes $2s+1$ with the constraint that $s$ satisfy certain congruence relations and Euler's idoneal numbers.

I would like to prove the following statement: If $s>1$ is a positive integer and $s\equiv0$ modulo 3 and $s\equiv0$ modulo 4 and $2s+1$ is prime then $2s+1 = x^{2}+24y^{2}$ for some ...
0
votes
1answer
40 views

Reference request for a divisibility property of Fibonacci numbers

Define the Fibonacci numbers $F_n$ by $F_n=F_{n-1}+F_{n-2}$ and initial values $F_0=0$ and $F_1=1.$ I would like to get a reference for the following result: If $p$ is a prime number with $p \equiv ...
0
votes
1answer
25 views

Confused about a simplification step in induction

Hello - I don't know how they got from the 3rd line to the 4th line. I understand all other parts of the simplification.
0
votes
1answer
50 views

proof - GCD and Number Theory

I have been trying to solve these but have had no success. Please help by giving hints not answers. Assuming that $\gcd(a,b)=1$ prove the following: (a) $\gcd(a+b,a-b)=1$ or $2$. [Hint: Let $d=...
2
votes
1answer
46 views

Divisibility of Binomial Coefficients by a Composite Number [duplicate]

I am aware of proof of divisibility of binomial coefficients of a prime $p$. I've seen it is easy to show that when $0<k<p$ $$\binom{p}{k}\equiv 0 \mod p$$ Can there be anything stronger. ...
3
votes
1answer
55 views

When does $\phi (n) \mid n $?

I need to find all the integers such that $\phi (n) \mid n $, where $\phi$ is the totient function. Using $$\phi(n)=n\prod(1-1/p)$$where the product runs over all prime factors of n, one gets that $$...
4
votes
1answer
42 views

a number n as pa+qb

How can we express a number $n$ as $pa+qb$ where $p \geq0$ and $q \geq 0$ and $p$ and $q$ can't be fraction. In contest I got a puzzle as if we can express $c$ as sum of $a$ and $b$ in form $pa+qb$. ...
5
votes
8answers
175 views

Prove that $6$ divides $n^3+11n$?

How can i show that $$6\mid (n^3+11n)$$ My thoughts: I show that $$2\mid (n^3+11n)$$ $$3\mid (n^3+11n)$$ And $$n^3+11n=n\cdot (n^2+11)$$ And if $n=x\cdot 3$ for all $x \in \mathbb{N}$ then: $$3\mid (...
7
votes
4answers
154 views

Prove that $8640$ divides $n^9 - 6n^7 + 9n^5 - 4n^3$.

I found this problem in a book, I can't solve it unfortunately. Prove that for all integer values $n$, $n^9 - 6n^7 + 9n^5 - 4n^3$ is divisible by $8640.$ So far I've noticed that $8460 = 6! \times 12$,...
4
votes
1answer
84 views

Probability that $7^m+7^n$ is divisible by $5$

If $m,n$ are chosen from the first hundred natural numbers with replacement, the probability that $7^m+7^n$ is divisible by $5$ is? $$7^m+7^n=7^m(1+7^{n-m}), n\ge m$$ The above expression is ...
0
votes
2answers
65 views

Let $p \in \mathbb{Z}$ so that if for all $a,b \in \mathbb{Z}$ where $p \mid (ab)$ is true then $p \mid a$ or $p \mid b$. Does this makes $p$ a prime?

I know this is related with Euclid's Lemma (the difference is that the lemma starts by assuming that $p$ is a prime which we don't here). I got this question in an exam and couldn't prove the ...
0
votes
0answers
28 views

When $n\mid\sum_{k=1}^{n}\phi (k)$

Consider this function. $$f(n)=\sum_{k=1}^{n}\phi (k)$$ where $\phi (k)$ is the Euler's totient function. I'm wondering are there infinitely many $n$ such that $n\mid f(n)$? For $n\leq 4000$ only ...
30
votes
0answers
749 views

How to solve this two simultaneous “divisibilities” : $n+1\mid m^2+1$ and $m+1\mid n^2+1$

Is it possible to find all integers $m>0$ and $n>0$ such that $n+1\mid m^2+1$ and $m+1\,|\,n^2+1$ ? I succeed to prove there is an infinite number of solutions, but I can not progress anymore......
0
votes
6answers
67 views

How can I prove that if $a^7 = b^7$ then $a=b$, with $ a,b \in \mathbb{Z} $

I've tried with divisibility, meaning that since $a$ divides $a^7$, then $a$ divides $b^7$ and in the same way b divides $a^7$, but I can't seem to go further than this. What properties of the ...
5
votes
1answer
113 views

Finding Divisibility of Sequence of Numbers Generated Recursively

I have the following generating function: $$E(x)=\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty {E_n}\frac{x^n}{n!}$$ which generates a sequence of integers below $$\{1, -1, 3, -15, 93, -725, 6815, -...
2
votes
1answer
51 views

Prove, that $13\mid 10a+b$, when $13\mid a+4b$. [closed]

Prove, that $13\mid 10a+b$, when $13\mid a+4b$. I have no idea where to start, all similiar problems I have solved yet involved two expressions that were given and this only has one. What am I ...
-1
votes
1answer
18 views

divisibility criterion for integer numbers using congruences

let be a positive integer written in the form $$ \sum_{n=0}^{k}a(n)10^{n} $$ my question is how can i deduce using mathematics if the number is divisible by 2 , 4 or another higher integer using ...
0
votes
1answer
49 views

Understanding “divides” notation (aka “|”) in “d | (k,n)”

I'm wondering what the notation under the sigma symbol means: I understand that d | k means that d divides k. However, I am unsure of what d | (k,n) means. Does this mean d divides both k and n? Or ...
5
votes
4answers
1k views

Factorial question: number of trailing zeroes in 125! [duplicate]

How many zeros are after the last nonzero digit of 125! ? The answer is 31, but how do you solve it?
1
vote
1answer
25 views

Dividing with imaginary numbers, simplifying

Alright, so I have $8-\frac{6i}{3i}$. I multiplied by the conjugate of $3i$, and got $-18-\frac{24i}{9}$. This is the part that confuses me, because I don't know how to divide this. Can I divide ...