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)

3
votes
2answers
48 views

How to prove that if $m$ is squarefree, then $d^2 \lvert mb^2 \implies d \lvert b$

This statement was given in my number theory textbook when analyzing quadratic fields, and I am not seeing how to prove it. $m$ is a squarefree (not divisible by the square of any number) integer and ...
0
votes
4answers
68 views

Dividing by Zero Using Exponents

I am sorry if I am missing some fundamental rule disproving my question, but I am very confused here. So $0^0 = 1$ and $x/x = x^0 = 1$ so if $x = 0$ $0/0 = 1$ The problem here is people have ...
4
votes
2answers
67 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 ...
1
vote
1answer
65 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
4
votes
3answers
428 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 ...
1
vote
2answers
28 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
4answers
199 views

Odd divisibility induction proof

Prove that for odd $n>3$ $$64\ | \ n^4-18n^2+17$$ I checked that for $n=5$ it works. I think I need to assume that for $2n+1$ it holds and show that $2n+3$ also holds. Any ideas?
2
votes
1answer
22 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
78 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 ...
1
vote
1answer
79 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 = ...
8
votes
0answers
85 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 ...
0
votes
3answers
31 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?
1
vote
4answers
61 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} \\ ...
5
votes
4answers
3k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
2
votes
5answers
112 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: ...
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 ...
3
votes
3answers
31 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
54 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
2answers
52 views

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$

If $a=b+c$ then $(a,b)=(a,c)=(b,c)$ I was thinking of writing the Euclidean algorithm \begin{align*}a &= b\cdot 1+c\\ b &= c\cdot (-1) + (b+c)\\ c &= a \cdot 1 + ...
2
votes
1answer
54 views

How to show that $\mathbb Z+x \mathbb Q[x]$ is a GCD domain?

How to show that $\mathbb Z+x \mathbb Q[x]$ is a Bezout domain, that is, the sum of two principal ideals is again a principal ideal ? Or at least, how to show that it is a GCD domain ? (This will then ...
1
vote
1answer
47 views

Looking for an example of a GCD domain which is not a UFD

I know that every UFD (unique factorization domain) is a GCD domain i.e. g.c.d. of any two elements, not both zero, exists in the domain. I am looking for an example of a GCD domain which is not ...
-3
votes
3answers
55 views

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

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
18 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 ...
0
votes
2answers
41 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
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?
3
votes
1answer
61 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. ...
10
votes
3answers
1k views

For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$?

Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$? In other words, does each $2^x-1$ introduce a new prime factor?
4
votes
1answer
37 views

Is there an $n$ such that $p|n^2+1$ with $2n<p<2n+\sqrt n$?

Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$? It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible ...
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
105 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
41 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
38 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
126 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
56 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
81 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
224 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.
6
votes
8answers
200 views

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

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
23 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
45 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
37 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
22 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
1answer
75 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
16 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 ...