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)

1
vote
2answers
29 views

if d divides n then prove that fibonacci of d divides fibonacci of n

prove that if $d$ divides $n$ then prove that fibonacci of $d$ divides fibonacci of $n$. i have tried to write $F(n)$ as a multiple of $F(d)$ using the fact that $n = ad$ for some natural $a$ but got ...
4
votes
3answers
440 views

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$.

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$. I am very new to proofs and not completely sure of how to approach this one. I tried several different ...
4
votes
2answers
70 views

Find all values of $x,y,z$ positive integers such that $4^x+4^y+4^z$ is a perfect square

I have to solve the equation $$4^x+4^y+4^z=k^2$$ I posted my solution but i don't know if there are other solution. How can i demonstrate that this expression is a perfect square? Are there oter ...
2
votes
1answer
24 views

Find remainder when $20^{13}$ is divided by $4940$

Find remainder when $20^{13}$ is divided by $4940$ I have solved this, but am hoping for an elegant solution. My solution: $r(20^{13}||4940) = 20 \times r(20^{12}||247)$ where $r(a||b)$ is the ...
3
votes
2answers
52 views

Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$

I have this review question for an exam and I was hoping someone can help me solve it: Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$ this is what I have so far, not sure if it is ...
1
vote
4answers
73 views

Let $a,b$ be relative integers such that $2a+3b$ is divisible by $11$. Prove that $a^2-5b^2$ is also divisible by $11$.

The divisibility for $11$ of $a^2 - 5b^2$ can be easily verified; in fact: $$a \equiv \frac {-3}{2}b \pmod {11}$$ therefore $$\frac {9}{4}\cdot b^2 - 5b^2 = 11(-\frac{b^2}{4}) \equiv 0 \pmod {11}.$$ ...
1
vote
9answers
79 views

Find integers $m$ and $n$ such that $14m+13n=7$.

The Problem: Find integers $m$ and $n$ such that $14m+13n=7$. Where I Am: I understand how to do this problem when the number on the RHS is $1$, and I understand how to get solutions for $m$ and ...
8
votes
0answers
92 views

Remainder of dividing $3^n$ by $2^n$.

I'd like to find the remainder of dividing $3^n$ by $2^n$, that is, I'd like to find value of $r$ in the expression $$3^n=q2^n+r,$$ where $q\in\mathbb{Z}$ and $0<r<2^n$. I know that it can be ...
1
vote
4answers
67 views

Why the $GCD$ of any two consecutive fibonnaci numbers is $1$?

Note: I've noticed that this answer was given in another question, but I merely want to know if the way I'm using could also give me a proof. I did the following: $$F_n=F_{n-1}+F_{n-2} \\ ...
1
vote
4answers
31 views

A={n∈ℤ: 6∣n and 8∣n} and B={n∈ℤ: 48∣n}. Is A⊆B?

A={n∈ℤ: 6∣n and 8∣n} and B={n∈ℤ: 48∣n}. Is A⊆B? Is B⊆A? I'm pretty sure that they are subsets of each other, because any n that 6 and 8 would both divide would have to be divisible by 6*8, but I'm ...
2
votes
5answers
116 views

Prove the existence or the non-existence of a couple of numbers ($n$,$m$) such that $n^2=m!$ [duplicate]

In recent days, while I was doing exercises on combinatorics, I thought if a number $m!$ could be a perfect square. I proved to demonstrate it through the prime factorization. My attempt: ...
3
votes
3answers
41 views

Prove the sum of any $n$ consecutive numbers is divisible by $n$ (when $n$ is odd).

Let $n \in \mathbb N$ be odd. Prove that the sum of any $n$ consecutive numbers is divisible by $n$. I started out with $s = x + (x + 1) + (x + 2) + … + (x + n) = kx + n.$ What I am interested in ...
-1
votes
3answers
56 views

show that $3^{(p-1)/2} +1$ is divisible by $p$ [closed]

let $n$ be an integer $>1$, and suppose that $p=2^n+1$ is a prime. Show that $3^{(p-1)/2} +1$ is divisible by $p$ (First show that $n$ must be even)
0
votes
3answers
32 views

Prove that if $ r,p \in \Bbb{N} $, then $ \gcd(r,rp) = r $.

Problem. Prove that if $ r,p \in \Bbb{N} $, then $ \gcd(r,rp) = r $. I tried solving this. If $ \gcd(r,p) = 1 $, then $ \gcd(r,rp) = 1 \times r $. Is that right?
-4
votes
3answers
63 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 ...
2
votes
1answer
20 views

Show that there exist $k$ and $r$ such that the given sum is divisible by $n$

Let $a_{1},\dots,a_{n}$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_{k}+a_{k+1}+\dots+a_{k+r}$$ is divisible by $n$. I am unable to find the necessary way to solve ...
1
vote
1answer
21 views

Find GCD in Q[√3] assuming it is defined

How do I find the GCD of 24 and 49 in the integers of Q[√3], assuming that the GCD is defined?
0
votes
2answers
44 views

Writing a GCD of three numbers as a linear combination

i know how to find the $\gcd(5,11,2^{2015}-1)$. but i can't seem to find the linear combination. do you find it the same way we find the linear combination of two integers.
1
vote
1answer
14 views

quadratic form polynomial divisibility vs. matrix pointwise multiplication.

Given matrix $V',W',Y'$ is of $d\times m (d\le m)$ ; column vector $c$ is of size $m$; $r_i, i=1,...,d$ are distinct; and each row of the matrix A is $A_i=(r_i^0 ... r_i^{d-1})$. So, A is of $d\times ...
3
votes
1answer
62 views

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $a+c\mid ab$ and $b+c\mid ab$

Find all $c\in\mathbb Z^+$ for which $\exists a,b\in\mathbb Z^+, a\neq b$ with $\begin{cases}a+c\mid ab\\b+c\mid ab\end{cases}$ For those $c$, prove only finitely many $(a,b)$ exist. ...
0
votes
2answers
56 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 ...
4
votes
5answers
106 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 ...
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
86 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
226 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
210 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 + ... + ...
2
votes
2answers
50 views

Properties of Greatest Common Divisors

I really want to have help verify these properties of GCD: Let $s,t \in \mathbb{Z}$ and $m,n$ be positive integers with $m\mid n$. If $\gcd(t,n)\mid\gcd(s,n)$, then $\gcd(t,m)\mid\gcd(s,m)$. If ...
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) ...
4
votes
1answer
24 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
4answers
39 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 ...
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
1answer
85 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.
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 ...
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
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 ...
1
vote
2answers
60 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 ...
4
votes
3answers
65 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
38 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
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
35 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 ...
1
vote
1answer
82 views

Fermat's Little Theorem and prime divisors

Let $a,b\in\Bbb N$ and $a+b$ be an even number. Assume $a^2 - b^2 - a$ is an exact square, say $c^2$. Let $m = \frac {a+b}2$ and $n = \frac {a-b}2$. Then, $$(4m-1)(4n-1) = 4(4mn-m-n) + 1 = ...
2
votes
1answer
42 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. ...
6
votes
2answers
103 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 ...
5
votes
1answer
114 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 ...
0
votes
5answers
95 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, ...