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

learn more… | top users | synonyms

34
votes
3answers
559 views
+200

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid ...
1
vote
1answer
40 views

Least Common Multiple and Greatest Common Divisor

Prove that if $\mathop{\mathrm{lcm}}( a, b) + \gcd(a, b) = a+b$, $a$ divides $b$ or $b$ divides $a$. This problem seemed simple at first, however I cannot figure out a way to prove this. If I assume ...
8
votes
1answer
965 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
9
votes
12answers
4k views

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$ This seems clear, but I don't know how to prove this.. I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then ...
0
votes
3answers
44 views

proof for divisibility

Prove without the use of congruences that $341$ divides $2^{340} - 1$. This was a question I found in a book right after which Fermat's little theorem is discussed. I tried using it for the proof but ...
0
votes
0answers
21 views

Divisibility in $\mathbb C[t]$

I am looking for all the polynomials $P,Q,R\in\mathbb C[t]$ such that $121P^2+614PQ+841Q^2-R^2$ divides $11P+29Q-R$. I remarked that $$121P^2+614PQ+841Q^2=(11P+29Q)^2-24PQ.$$ So, ...
2
votes
1answer
74 views

Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?

I was wondering if anyone has any insights regarding the fact that the sum of any $a_1, \dots, a_{10}$ consecutive Fibonacci numbers is divisible by $11$ (and furthermore equals to $a_7*11$). What can ...
1
vote
0answers
28 views

Is this :$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $ irrational series for every natural number $k$?

Is this: $$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $$ irrational series for every natural number $k$? Where : $\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of ...
1
vote
2answers
33 views

$k | x^{k} - x,$ for $k, x \in \mathbb{Z}$?

I seem to have found that: $$k | x^{k} - x, \ \text{for} \ k, x \in \mathbb{Z}.$$ I have tried it with a few values, and it seems to be true. I am sure that this has been discovered before.
3
votes
4answers
50 views

How do I show that we can't write $N=114^n-1$ as sum of $3$ squares for all natural number $n>2$?

I run some computations in wolfram alpha, I see that we can't write :$$N=114^n-1$$ as sum of $3$ squares, then Hop someone who can show me how I do prove that we can't write $N=114^n-1$ as sum of $3$ ...
12
votes
5answers
3k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
0
votes
0answers
43 views

Divisibility Question [duplicate]

If $(ab+1)$ divides $(a^2+b^2)$ then prove that $(a^2+b^2)$ when divided by $(ab+1)$ gives a square of an integer.
6
votes
5answers
79 views

Show that $4$ does not divide $x^3-2$

Show that $4$ does not divide $x^3-2$ is what I need to prove. I think I should put $4k$ is $x^3-2$ and then contradict it somehow. Alternatively is to factor it out as $x^3$ is $x(x+2)(x-2)$ but I ...
0
votes
1answer
26 views

How do I show that :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number?

How do i show this if it's not an open problem :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number and p is prime number. and $\sigma({p^m})$ is sum divisors of $p^m$ ...
2
votes
2answers
97 views

Prove that rational numbers $a,b$ are integers if $a+b$ and $ab$ are integers

I have been trying to prove this via divisibility, assuming that $a=\frac{n}{m}$ and $b=\frac{r}{q}$ for some $n,m,r,q$ in Ints($m$,$q$ not $0$), but I'm completely stuck here. Any help?
1
vote
1answer
41 views

When does :$\sigma(\sigma(2n))=\sigma(\sigma(n))$ and $\sigma(n)$ is sum divisors of the positive integer $n$?

Is there someone who can show me When does: $$\sigma(\sigma(2n))=\sigma(\sigma(n))$$ where : $\sigma(n)$ denote the sum divisors of the positive integer $n$ ? Note (1) : I accrossed this problem when ...
0
votes
1answer
58 views

Prove: If $d|a$ and $d|b$ then $d^2|ab$

Prove: If $d|a$ and $d|b$ then $d^2|ab$ All I have $ab = kd^2$, $k$ some integer. I'm stuck and hoping someone could walk me through this!
6
votes
3answers
538 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
-5
votes
1answer
44 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = ...
0
votes
1answer
44 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is ...
3
votes
2answers
35 views

Numbers divisible by all of their digits: Why don't 4's show up in 6- or 7- digit numbers?

For reasons I'll explain below the question if you're interested, I stumbled across a peculiar phenomenon involving numbers divisible by their digits. I'm concerned with numbers that are divisible by ...
0
votes
1answer
15 views

Determine overall ratio from individual ratios

I have a set of statistics that I need to find the overall ratio to. This example will work with only two items so I'll write them down: ...
0
votes
2answers
52 views

Why is it true that if $ax+by=d$ then $\gcd(a,b)$ divides $d$?

Can someone help me understand this statement: If $ax+by=d$ then $\gcd(a,b)$ divides $d$. Bezout's identity states that: the greatest common divisor $d$ is the smallest positive integer that ...
0
votes
0answers
73 views

Moving up the Y axis the length of the hypotenuse of a right triangle

If I have a right $\triangle ABC$ with $B$ being the right angle and length $AB = 50$ and length $BC = 50$. Based on the Cartesian coordinate system if I wanted to move up the Y axis the length of the ...
1
vote
1answer
39 views

How to use the division algorithm to prove these form of integers?

I have in my notes the form of the integers as: Now, I know that I have to use the division algorithim to prove the first form, and I can do this, but in the second form of an integer $4k$ isn't the ...
2
votes
5answers
83 views

Proving $n^3 + 3n^2 +2n$ is divisible by $6$

The full question is: Factorise $n^3 + 3n^2 + 2n$. Hence prove that when $n$ is a positive integer, $n^3 + 3n^2 + 2n$ is always divisible by $6$. So i factorised and got $n(n+1)(n+2)$ which i think ...
6
votes
5answers
922 views

Prove that there is no number that divides both n and n+1

Statement There is no number $x > 1$ that divides both $n$ and $n+1$. Proof (my attempt) Indirect proof: \begin{align} x\mathbin{\vert} n & \implies n = xt_1 \\ x\mathbin{\vert}(n+1) ...
0
votes
1answer
22 views

The lowest number that is divisible by a and b

I have the numbers $a = 120, b = 144$. So if I prime them I get $120 = 5\times3\times2\times2\times2$ and $b = 144 = 2\times3\times3\times2\times2\times2$. I am looking for the lowest number that is ...
3
votes
3answers
51 views

Is this formula true for $n\geq 1$:$4^n+2 \equiv 0 \mod 6 $?

Is this formula true for $n\geq 1$:$$4^n+2 \equiv 0 \mod 6 $$. Note :I have tried for some values of $n\geq 1$ i think it's true such that :I used the sum digits of this number:$N=114$,$$1+1+4\equiv ...
2
votes
1answer
23 views

A question about the divisibility of certain polynomial sequences.

$2n+1=(n+1)^2-(n)^2$ . Therefore $(n+1)^2-n^2$ never divides $2$ for any integers.Can we make a similar statement for $(n+1)^x-n^x=a_n$ ... And if we can, can we combine polynomials to give us a ...
0
votes
1answer
24 views

Form of Divisors of Proth numbers

Proth number is a number of the form : $z⋅2^k+1$ where z is an odd positive integer and k is a positive integer such that : $2^k>z$ Is there a form for divisors of Proth Numbers? (Like Mersenne ...
2
votes
2answers
155 views

Divisibility question

Prove: (A) sum of two squares of two odd integers cannot be a perfect square (B) the product of four consecutive integers is $1$ less than a perfect square For (A) I let the two odd integers ...
1
vote
5answers
49 views

Divisibility theory help

If $a$ is odd, show that $32 \mid (a^2 + 3)(a^2 + 7)$ Since $a$ is odd, I let $a = 2b + 1$ and did the expansion to get $16\mid [(b^2 + b +1)(b^2 + b + 2)]$, but I was unable to continue from ...
1
vote
0answers
43 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
3
votes
1answer
64 views

Frazzle game question

In $7^{th}$ grade, in order to learn divisibility, memory, and focus, my math teacher had my pre-algebra class play a game called Frazzle. To play the game Frazzle, each person went around the room ...
1
vote
0answers
28 views

Example of binary GCD for complex integers?

I know you can use bit shifting to speed up the GCD algorithm for a pair of integers. Is there a way to apply this idea to gaussian integers?
4
votes
2answers
30 views

GCD of many numbers divisible by another number

$a$ is an integer such that: $$a \mid \gcd(b_1,b_2,\ldots,b_z)$$ and $z$ can be very large. Does the GCD approach $a$ as $z$ grows? If yes, what is the relation between $z$ and $a$? Thanks...
1
vote
1answer
51 views

Can we always write $gcd(x,y)$ as $ax+by$ in UFD?

Let $R$ be a commutative ring with unity. Now assume that $R$ is Unique Factorization Domain, but not necessarily Principal Ideal Domain. Question: Let $x,y\in R$ be such that their GCD exists in ...
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 ...
1
vote
2answers
45 views

Is it true that $(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1$?

Notation: $(a,b) = \gcd(a,b)$ If $p,q$ are distinct odd primes, is it true that $$(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1\;?$$
4
votes
4answers
91 views

prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$

I'm trying to prove that $\operatorname{lcm}(n,m) = nm/\gcd(n,m)$ I showed that both $n,m$ divides $nm/\gcd(n,m)$ but I can't prove that it is the smallest number. Any help will be appreciated.
1
vote
3answers
62 views

HCF of two huge numbers

A question goes like : Find the HCF of $\underbrace{111\ldots 11}_{100\text{ ones}}$ and $\underbrace{111\ldots11}_{60 \text{ ones}}$. The answer is $\underbrace{111\ldots11}_{20 \text{ ones}}$ I'd ...
1
vote
4answers
87 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
0
votes
0answers
31 views

Rabin's cryptography - when the message $M$ isn't coprime to $n = pq$

Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$? say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$. ...
1
vote
3answers
541 views

Simple Property of GCD and Modular Arithmetic

I'm stuck on proving a rather elementary property, as I'm not really sure how to start off the approach. Suppose $g^a\equiv 1$ mod $m$ and $g^b\equiv 1$ mod $m$. Does this imply that ...
46
votes
4answers
7k views

Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$

For all $a, m, n \in \mathbb{Z}^+$, $$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$
2
votes
2answers
208 views

Fermat's little theorem

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
0
votes
3answers
55 views

Are there any divisibility rules using 7? [duplicate]

Divisibility rules of 1,2,3,4,5,6,8,9 are first or second grade math. Are there any divisibility rules for numbers with factors including 7. I noticed that the digits of 7x starting with x=1 to x=5 ...
2
votes
2answers
68 views

Number Theory- Mathematical Proof

I am trying to prove a theorem in my textbook using another theorem. What I need to show that if a,b, and c are positive integers, show that the least positive integer linear combination of a and b ...
1
vote
1answer
94 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...