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

learn more… | top users | synonyms

12
votes
2answers
1k views

Elementary proof of Zsigmondy's theorem

I've been writing a not-so-short introduction to elementary number theory, supplying proofs for all theorems. When coming across Zsigmondy's theorem, it seemed difficult to find a proof available on ...
4
votes
5answers
108 views

Proof that $(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$ is a multiple of $3$.

I proved that $$(n^7-n^3)(n^5+n^3)+n^{21}-n^{13}$$ is a multiple of $3$ through the use of Little Fermat's theorem but i want to know if there exist other proofs(maybe for induction). How can I ...
0
votes
2answers
66 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
3
votes
1answer
60 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)$ ...
6
votes
1answer
145 views

Product of consecutive Fibonacci numbers divisibility

Prove that the product of any $k$ consecutive Fibonacci numbers is divisible by the product of the first $k$ Fibonacci numbers. We can try to show that for every prime $p$, the power of $p$ appearing ...
1
vote
1answer
38 views

Analytical solution for $\max{x_1}$ in $(x_n)_{n\in\mathbb{N}}$

Let be $x_1,x_2,x_3,\ldots,$ a sequence of positive integers. Suposse the folowing conditions are true for all $n\in\mathbb{N}$ $n|x_n$ $|x_n-x_{n+1}|\leq 4$ Find the maximun value of $x_1$ I ...
1
vote
4answers
62 views

How find the fractional part of $5^{200}$ divided by $8$?

Finding the fractional part of $\frac{5^{200}}{8}$. I've had this problem given to me (we're learning the Binomial Theorem and all.) So obviously I thought I'd apply the binomial theorem to it, ...
1
vote
2answers
91 views

Contest Problem - Divisibility

Find all ordered pairs (x, y) of positive integers x, y such that $x+y$ divides 2014 and (simultaneously) $x^yy^x$ divides $(x+y)^{(x+y)}$ . This is a contest problem from U Tenn, FERMAT contest. My ...
6
votes
11answers
227 views

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$. [closed]

Prove that $n^2(n^2+1)(n^2-1)$ is a multiple of $5$ for any integer $n$. I was thinking of using induction, but wasn't really sure how to do it.
5
votes
8answers
214 views

Why is $n^2+4$ never divisible by $3$? [duplicate]

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
2
votes
1answer
31 views

Proving divisibility of $\sum\limits_{r=1}^{p-1} {r^{p^n}}$ by p.

Let $p>2$ be an odd number and let $n$ be a positive integer. Prove that $p$ divides $${\sum\limits_{r=1}^{p-1}{r^{p^n}}}$$ My Proof: From multinomial expansion, we know that $${(1 + 2 + 3 + ... + ...
20
votes
4answers
2k views

Is the number $333{,}333{,}333{,}333{,}333{,}333{,}333{,}333{,}334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to $0$ or $1$ (mod $4$). Now since the number is even, I know that it is either $0$ or $2$ (mod $4$). How would I go about ...
4
votes
1answer
25 views

Square Roots: Variables with Exponents.

Alright, so let me get this straight: $\sqrt{x^2} = |x|$ $\sqrt{x^3} = x\sqrt{x}$ $\sqrt{x^4} = x^2$ $\sqrt{x^6} = |x^3|$ Are these correct?
0
votes
2answers
47 views

divisibility of complex numbers

I want to show that $(a + bi)|(c + di)$ is equivalent to the statement that the ordinary integers $(a^2 + b^2)|(ac + bd)$ and $(a^2 + b^2)|(-ad + bc)$. I also want to show that $(a + bi)|(c + di) ...
10
votes
4answers
169 views

Divisibility of $6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$

Prove or disprove that for all natural $n$ $$6^{2^n}+ 8^{2^n} +12^{2^n}+14^{2^n}+16^{2^n}+18^{2^n} +24^{2^n} +28^{2^n}+42^{2^n}$$ is divisible by $259$. I tried to apply mathematical induction, but ...
0
votes
4answers
40 views

Question on modulus

Is $x|y$ the same as $x \equiv 0\! \mod\!{y}$ ? If not then how should it be written?
1
vote
2answers
23 views

Find the largest size of squares that can pave a given rectangle

The floor of a hall 252cm long, 162cm wide is paved with equal squares. Find the largest size of marble and number required, if only whole marbles are used. See the attempted solution posted as ...
3
votes
1answer
102 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.
1
vote
0answers
17 views

$x\in\mathcal{O}_K$ can be written as product of irreducible elements

Lemma: Every element $x\neq 0$ of $\mathcal{O}_K$ with ($K$ an arbitrary number field) can be written as a product of irreducible elements. Proof: We prove this lemma by complete induction on ...
1
vote
4answers
63 views

Is $\gcd(2^{2n}+1, 3)=1$?

Can any one prove that $2^{2n}+1$ and $3$ are relatively prime for any integer $n$? I tried with a Matlab program and computed this gcd upto $n= 25$. I got 1 for all of them. So I suppose that the ...
1
vote
2answers
61 views

Interesting $0, 1$ sequence of numbers,after $n>2, a_n$is composite.

Let us have a finite sequence with only $0$ and $1$ digit in our numbers(it can begin with $0$ too). $a_n$ is the number, which we get if we write our number $n$ times next to each other. Prove, that ...
1
vote
2answers
44 views

If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime?

The Statement of the Problem: If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime? My Thoughts: I know that the answer is that $n$ must be odd. However, I'm not sure how ...
6
votes
2answers
106 views

Pythagorean Triples : Is every positive integer $\gt$ $2$ part of at least one Pythagorean triple?

I was doing some basic number theory problems from Rosen and came across this problem: Show that every positive integer $\gt$ $2$ is part of at least one ...
4
votes
3answers
66 views

Prove that ${x^2+y^2=z^n}$ has a solution in $\mathbb{N}$ for all $n$ in $\mathbb{N}$

I am solving it by stating that $$x^2 +y^2 =c^2$$ represents a circle. And when $$c^2=z^n$$ then , it represents a system of concentric circles with radius varying as $z$ varies or $n$ varies. So, for ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
1
vote
2answers
39 views

GCD theory - gcd(x, y) = 1

Take $n + 1$ numbers out of $1, 2, ..., 2n$. Show that there will be two numbers $x, y$ so that $gcd(x, y) = 1$. What I've got is: Let $d=gcd(a,b)$; by definition there are integers $a′$ and $b′$ ...
2
votes
2answers
47 views

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I'm not sure how to use that information if I even can to show that $p^n \mid ...
2
votes
1answer
36 views

Example of a domain where all irreducibles are primes and that is not a GCD domain

One has the following relations for a domain $R$: $R$ GCD domain $\Rightarrow$ All irreducible elements are prime $R$ PID $\Rightarrow$ $(R$ GCD domain $\land$ $R$ statisfies ACCP$)$ $R$ UFD ...
2
votes
1answer
81 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that ...
2
votes
1answer
23 views

Prove that if $a, b, n\in \mathbb{N}, n\geq2\longrightarrow \sqrt[\leftroot{-2}\uproot{2}n]{a}\in \mathbb{Q} \iff a=b^n$.

Prove that if $a, b, n\in \mathbb{N}, n\geq2\longrightarrow \sqrt[\leftroot{-2}\uproot{2}n]{a}\in \mathbb{Q} \iff a=b^n$. I'm at a complete loss here, I tried using the order of a prime function but ...
2
votes
1answer
46 views

An expression with gcd and abs is transformed magically!

There's a problem to calculate $\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{|i-j|}{\gcd(i,j)}$, whose tutorial gives the following transformation I really don't understand. ...
5
votes
1answer
115 views

Pythagorean Triples : Show that exactly one of $x$, $y$, and $z$ is divisible by $5$

I was doing some basic number theory problems from Rosen and came across this problem: Show that if $(x, y,z)$ is a primitive Pythagorean triple, then exactly one of $x$, $y$, and $z$ is divisible ...
10
votes
5answers
324 views

Show that $\gcd\left(\frac{a^n-b^n}{a-b},a-b\right)=\gcd(n d^{n-1},a-b)$

How to show that $$ \gcd\bigg( {a^n-b^n \over a-b} ,a-b\bigg )=\gcd(n d^{n-1},a-b ) $$ $a,b\in \mathbb Z$ where $d=\gcd(a,b)$? Note $\ $ Some of the answers below were merged from this ...
5
votes
16answers
4k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
3
votes
1answer
58 views

Number of pairs $(A,B)$ with $\gcd(A,B)=B, A \ne B^2$ with $A,B \le n$

How many pairs $(A,B)$ of integers up to $n$ are there such that $\gcd(A,B)=B$, not counting those pairs where $B^2=A$? If we consider $n = 5$ we have $25$ possible pairs. They are ...
0
votes
5answers
100 views

Mathematical induction [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...
1
vote
5answers
101 views

Proving $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ [duplicate]

I'm trying to prove by MI. I have already distributed n+1, but now I'm stuck on how I can show 9 divides the RHS since $42n$ and $3n^3$ does not divide evenly. ...
0
votes
3answers
432 views

Mathematical induction prove that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ . [duplicate]

How can I use mathematical induction to prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a nonnegative integer?
5
votes
5answers
4k views

Simple Proof by induction: “9 divides $n^3 + (n+1)^3 + (n+2)^3$”

I'm trying to prove using induction that 9 divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have: Base case: P(1) = (1) + (8) + (27) = 36, 36 can be divided by 9 ...
5
votes
4answers
1k views

How many integers in the range [1,999] are divisible by exactly 1 of 7 and 11?

This is a question in Kenneth Rosen's Discrete Mathematics textbook 6th edition. I haven't had trouble with any other counting problems regarding "how many numbers in range [x,y] have divisibility ...
2
votes
1answer
46 views

Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$. I am not even sure what tags to use because I am not sure of right methods to ...
12
votes
7answers
8k views

The product of n consecutive integers is divisible by n factorial

How can we prove that the product of n consecutive integers is divisible by n factorial? Note: In this subsequent question and the comments here the OP has clarified that he seeks a proof that ...
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 ...
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
18 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 ...
6
votes
2answers
797 views

Fibonacci and Lucas identity

By the trial and error method I have observed the following identity by taking some numerical values. Those are $F_m$|$L_n$ is valid only if one of the following holds. a) $m = 1$ or $m =2$ b) $m ...
1
vote
1answer
400 views

Proof by induction involving fibonacci numbers

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims: (i) For each $n≥0$, $f_{3n}$ is even. (ii) For each ...
11
votes
4answers
385 views

Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$

I can't crack this one. Prove: If $\gcd(a,b,c)=1$ then there exists $z$ such that $\gcd(az+b,c) = 1$ (the only constraint is that $a,b,c,z \in \mathbb{Z}$).