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

learn more… | top users | synonyms

5
votes
2answers
128 views

Is $a=\frac{1992!-1}{3449\times 8627}$ a prime number?

Is $a=\dfrac{1992!-1}{3449\times 8627}$ a prime number ? This is a natural follow-up to that recent MSE question We know that $a$ has $5702$ digits and no prime divisor $<10^6$.
0
votes
2answers
23 views

Explain 'expressing a number using its digits'

While studying divisibilty and prime numbers in my maths book (IB Mathematic Higher Level Option 10: Discrete Mathematics), I came across an explanation of a way to '[express] a number using its ...
-2
votes
1answer
39 views

How would you divide a polynomial by another polynomial whose power is greater than its nominator? [on hold]

I have a polynomial which is: $$\frac{(x^3-4x)}{(4x^2-4x+1)} = -10$$ Is there a way to do this? I have thought about doing long division which was not helpful...
1
vote
1answer
42 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 ...
0
votes
3answers
45 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
76 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$ ...
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
80 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 ...
2
votes
2answers
98 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?
0
votes
1answer
27 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$ ...
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 ...
36
votes
3answers
597 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 ...
0
votes
1answer
60 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!
-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 ...
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 ...
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
24 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 ...
2
votes
2answers
156 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 ...
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
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 ...
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
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=$ ...
2
votes
2answers
211 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 ...
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
70 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
14 views

Is there a way to figure out the number of possible combinations in a given total using specific units

I'm not professional mathematician but I do love a math problem - this one, however has me stumped. I'm a UX Designer trying to figure out some guidelines for using tables in a page layout. The thing ...
1
vote
0answers
50 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
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= ...
0
votes
3answers
55 views

Find remainder of $\frac{17^{235}}{ 23}$

I need to find remainder of $\frac{17^{235}}{ 23}$. This is supposed to be solved using the following method: $\varphi(23) = 22$ ${17}^{235} = (({17}^{22})^{10})\cdot {17}^{15}$ ${17}^{22}\equiv 1 ...
0
votes
1answer
38 views

Division with dividend less than divisor

Let $a\geq b$. We define the division of $a$ by $b$ to be, $$a=bq+r,$$ where $q,r$ are integers and $0\leq r<b$. How we divide $a$ by $b$ when $a<b$.?
0
votes
0answers
12 views

Given An initial point and final point ,How to determine the number of Co-Ordinates(x,y) such that both x and y are integral?

I have thought a lot about it and still no clue. I thought of visualising the initial point and the end point in the form of a Grid. But ,soon I was over with my resources. Problem: Given an initial ...
5
votes
3answers
110 views

If $a^b=c^d$, then $c$ and $a$ are powers of the same number?

I want to know in which situations two numbers that can be expressed as powers can be equal. I think it's intuitive that if two powers (say $a^b$ and $c^d$) are equal, then the bases must be ...
1
vote
1answer
26 views

Do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm?

As the title says, do we need to apply the Euclidean Algorithm before applying the Extended Euclidean Algorithm? For example, we have $\gcd(24,17)$, so we can find $x,y$ such that $24x+17y=1$. ...
0
votes
2answers
495 views

Question of remainder on dividing by 7

Question : What is the remainder when $$ 10^{10} + 10^{10^2} +10^{10^3} + \ldots + 10^{10^{100}} $$ is divided by $7$?
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 ...
3
votes
2answers
549 views

The sum of digits of $3(3x+3)$ is always $9$ for any $x$ between $1$ and $9$

Given the following 'joke' I stumbled across today It's easy enough to figure out that the answer is always 9. Asshole. However when I tried to 'prove' this for ...
2
votes
5answers
309 views

Triple fractions

I've got this simple assignment, to find out the density for a give sphere with a radius = 2cm and the mass 296g. It seems straightforward, but it all got hairy when i've got to a fraction with three ...