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)

4
votes
2answers
58 views

Proper divisors of 1?

What are the proper divisors of 1? I understand proper divisors do not include the number itself, but is 1 an exception or does it have no proper divisors?
7
votes
4answers
100 views

Show $17$ does not divide $5n^2 + 15$ for any integer $n$

Claim: $17$ does not divide $5n^2 + 15$ for any integer $n$. Is there a way to do this aside from exhaustively considering $n \equiv 0$, $n \equiv 1 , \ldots, n \equiv 16 \pmod{17}$ and showing $5n^2 ...
1
vote
1answer
56 views

Finding the inverse modulo . $7^{-2}\pmod {11}$ and $7^{-3}\pmod {11}$

$7^{-1}\pmod{11}$ the above can be found by $7x\pmod{11}\equiv 1$ and $x=8$ now i am confused on how to find $7^{-2}\pmod{11}$ and $7^{-3}\pmod{11}$ .
1
vote
2answers
55 views

Show that for every $n > 1$ there exist $n$ consecutive composite numbers [duplicate]

So I am trying to prove that for every $n > 1$ there exist $n$ consecutive composite numbers but I do not know even how to start. This is a problem in analytic number theory. Please can you help ...
2
votes
2answers
22 views

proof : $a,b \in N, a^5 | b^5 \rightarrow a | b$

I couldn't find anything to use apart from the fundamental theorem of arithmetic. Here is my proof : Let $a,b \in N$ Suppose $a^5 | b^5$ Let $S = \{ \text{ n is prime } , n | a \lor n | b \} $ $ ...
3
votes
3answers
96 views

How can I demonstrate that $x-x^9$ is divisible by 30?

How can I demonstrate that $x-x^9$ is divisible by $30$ whenever $x$ is an integer? I know that $$x-x^9=x(1-x^8)=x(1-x^4)(1+x^4)=x(1-x^2)(1+x^2)(1+x^4)$$ but I don't know how to demonstrate that ...
1
vote
5answers
51 views

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$ Ideas: I need to find integer $m$ such that $m=\frac{k!}{3^7}$ and $m\neq\frac{k!}{3^8}$, but I have 2 unknowns so don't know how to proceed from here. ...
0
votes
1answer
70 views

Division rules for other number systems?

How could we make the same division rules for other number systems, like in our decimal system: a number is divisible with 2 if it's last digit is 0,2,4,6,8, by 3 if the sum of digits is divisible ...
0
votes
1answer
30 views

$\operatorname{lcm}(a,b) = c$ and $\gcd(a,b) = d$ => $\operatorname{lcm}(\frac{a}{d},\frac{b}{d}) = \frac{c}{d}$ in a Euclidean domain or PID

I know that in an integral domain $c=\operatorname{lcm}(a,b)$ if and only if $a\mid c, b\mid c$ and if there exists $c'$ such that $a\mid c', b\mid c'$ then this implies that $c\mid c'$. And ...
4
votes
1answer
86 views

Finding missing digits in factorials

14!=871a82b1200 without working out 14!, find a and b I think it has something to do with maths rules regarding 9 or 3 (the digits adding up to either of those numbers) but not entirely sure!
2
votes
1answer
50 views

What does a distributed lattice have to do with GCD and LCM?

$\newcommand{\lcm}{\operatorname{lcm}}$I am lost while following this explanation: Let $$A(g, i) = \gcd(F_{g}, \lcm(F_{a_1}, F_{a_2}, \ldots , F_{a_i}))$$ and $$X = \lcm(F_{a_1}, F_{a_2}, \ldots , ...
1
vote
1answer
34 views

Divisibility problem using Wilson's theorem: $4(p-3)! + 2$ is divisible by $p$

Prove that $4(p-3)! + 2$ is divisible by $p$, where $p$ is an odd prime. Use Wilson's theorem. I am having trouble trying to bring it in the form where Wilson's theorem can be applied. Any help ...
0
votes
0answers
40 views

Put this word problem into math terms: A man goes to a stream…

A man goes to a stream with an 18-pint container and a 26-pint container. Using only these two containers: a) How does he get 2 pints of water into the larger container? b) What are all the ...
2
votes
1answer
28 views

Prove that for positive integers a, b, c, and d such that b != d, if gcd(a, b) = gcd(c, d) = 1 then a/b + c/d is not an integer. [duplicate]

I attempted this by assuming that a/b + c/d is an integer and coming to a contradiction, but I got stuck. Any hints?
6
votes
4answers
146 views

Efficiently producing certain kinds of examples of the application of Euclid's algorithm

Is there some efficient way to churn out pairs of integers $n,m$ such that $\gcd(n,m)=1$; $n,m$ both have fairly large numbers of fairly small prime factors; and Euclid's algorithm applied to $n,m$ ...
2
votes
9answers
86 views

Prove that if $a, b$ are any positive integers $>1$, then either $a$ or $b$ or $a+b$ or $a-b$ is divisible by 3.

I checked all the integers from $1$ to $1000$ manually, I don't know exactly how to prove this but any simple and easy proof would be appreciated. Thanks.
0
votes
1answer
59 views

Arithmetic mean 6 times greater than GCD?

I am not sure how to find an answer to this question. Is there a way to solve it without simply trial and error? Do there exist ten distinct positive integers such that their arithmetic mean is (a) ...
4
votes
2answers
66 views

GCD of many numbers

Given $a_1,...,a_n$ $gcd(a_1,...,a_n) = b$ I need to find $i$, so if i apply euclids algorithm to $(a_1,a_i)$, i end with $(0,b)$ or $(b,0)$.
2
votes
4answers
52 views

How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd. Firstly, $k \geq 1$ I can see induction is the best idea: Show for $k=1$: $2^{2^1} + 5 = 9 , 2^{2^1} + ...
0
votes
2answers
52 views

Why doesn't x/0 = ±∞ [duplicate]

I was watching a video on numberphile about dividing by 0 and It said that x/0=Undefined or Error since it could be + or - ∞. ...
1
vote
2answers
23 views

Proof dealing with greatest common divisors

I'm working on a proof which concludes that if $a\equiv b (mod\ m)$ then $gcd(a,m) = gcd(b,m)$ I know that we can rewrite the congruence as $km = a-b$ for some $k \in \mathbb{Z}$ I rearranged the ...
1
vote
3answers
95 views

Prove for positive integers a,b,c and d (where b does not equal d), if gcd(a,b) = gcd(c,d) = 1, then a/b + c/d is not an integer

I understand that if gcd(a,b) and gcd(c,d) = 1, at least one number in each pair is a prime or is 1. As for after that, I'm totally stumped, could I get some tips, clues, help?
2
votes
3answers
38 views

Prove for integers a, b, and c, if gcd(a, b) = 1, a|c, and b|c then ab|c

Prove for integers $a$, $b$, and $c$, if $\gcd(a, b) = 1$, $a|c$, and $b|c$ then $ab|c$. Part b of this question is: "Is the converse true? Prove or disprove accordingly?" Hey, so I've been drawing ...
3
votes
4answers
96 views

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$. This is what I was attempting or trying: Let $d =$ gcd$(a,b)$. $d|a ...
0
votes
0answers
18 views

GCD and fraction problem

If x/y = 1/a + 1/b + 1/c and GCD of a , b and c is 9 then find a) minimum of x and y which do not cause x/y repeating decimal b) the best of x and y that cause x/y nearly to 3/10 many ...
2
votes
2answers
49 views

Find all numbers of form $10^k+1$ divisible by $49$

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.
0
votes
0answers
29 views

Determine when a prime divides this

Let $x$ and $y$ be integers, and consider the expressions $A=192x+a$ and $B=192y+b$, where $a,b$ are nonnegative mod $192$ residues (so $a,b\in \{0,1,2,...,191\}$). For which ordered pairs $(a,b)$ ...
0
votes
1answer
52 views

Principal Ideal Ring and ID

In definition of PID, if we take ring instead of ID call it PIR. I add one more condition: all generators of an ideal are associate to each other. Would it imply PIR with this condition is PID? ...
0
votes
1answer
141 views

prime implies irreducible

In unique factorization ring with unity(I am not considering commutativity and zero divisor in definition of UFD) irreducible implies prime. And it was proved in ring with unity without zero ...
4
votes
2answers
43 views

What is sum of totatives of n(natural numbers $ \lt n$ coprime to $n$ )?

Same question as in title: What is sum of natural numbers that are coprime to $n$ and are $ \lt n$ ? I know how to count number of them using Euler's function, but how to calculate sum?
0
votes
1answer
56 views

UFD, prime and Irreducible

I am taking following definitions and calling algebraic structure U1 and U2 definition as: U1 is A ring R with unity and properties properties Every element of R is neither 0 nor a unit can be ...
0
votes
1answer
82 views

Prime element in ring without unity

Definitions of prime element: $(1)$ We say $p$ is prime if $p|ab$ it implies $p|a$ or $p|b$ (I don't need definition of unity here) $(2)$ We say $p$ is prime if $p=ab$ it implies $p|a$ or $p|b$ (I ...
3
votes
2answers
68 views

How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility. Example: Find the first Fib number that is divisible by $x=223321$, with no ...
3
votes
1answer
61 views

When is $(12x+5)/(12y+2)$ not in lowest terms?

I am struggling to solve this problem and would appreciate any help: When is $\frac{12x+5}{12y+2}$ NOT in lowest terms? (x,y are nonnegative integers) I have found that it is not in lowest terms for ...
1
vote
2answers
44 views

Linear congruence fill in the missing step?

Currently working on this problem and I'm having trouble seeing how it goes from one line to the next. $45x \equiv 63\mod 11$ goes to $x \equiv 8\mod 11$ Any help would be awesome thanks. ...
1
vote
3answers
60 views

If p is an odd prime, prove that $a^{2p-1} \equiv a \pmod{ 2p}$

Let $m = 2p$ If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$. I have no idea on how to start. I was trying to find a form such that $a^{m - 2} ...
0
votes
1answer
26 views

Does $ p|(2^{2kq}-2^{kq}+1)$ where $p=1+k\cdot q$ ? I'm stuck…

Does $ p|(2^{2kq}-2^{kq}+1)$ ,$p=1+k\cdot q$,where $p,q$ are prime ? From Fermat's little theorem; $(2^{2kq}-2^{kq}+1)$ mod $q\equiv (2^{2k}-2^{k}+1)$ This is where I'm stuck, please help. Thank ...
4
votes
1answer
75 views

Prove that $(z^3-z)(z+2)$ is divisible by $12$ for all integers $z$

I am a student and this question is part of my homework. May you tell me if my proof is correct? Thanks for your help! Prove that $(z^3-z)(z+2)$ is divisible by $12$ for all integers $z$. ...
0
votes
1answer
29 views

Number theory hcf confusion

I need to show 11|(100a+b) if and only if 11|(a+b). The solution: 11|(100a+b) iff 11|(100a+b-99a) so obviously 11|(a+b) and we have the solution as easily as that. However I cannot see why this is ...
0
votes
0answers
21 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 ...
3
votes
3answers
92 views

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ that is $a^{2n-1}\mid b^{2n} ; b^{2n}\mid a^{2n+1} , \forall n \in \mathbb Z^+$ , then is it true that $a=b$ ?
1
vote
1answer
35 views

$n,a,b \mathbb \in \mathbb Z^+$ , such that $n\mid a^n-b^n$ ; to show $n\mid \frac {a^n-b^n}{a-b}$ [duplicate]

Let $n,a,b \in \mathbb Z^+$ be such that $n\mid a^n-b^n$ , then how to prove that $n\mid {\dfrac {a^n-b^n}{a-b}}$ ? My try : $d=\gcd(n,a-b),$ so $d \mid{\dfrac {a^n-b^n}{a-b}}.$ Also $\,n ...
2
votes
3answers
61 views

Number Theory Simple Proof Confusion

Suppose that c|ab and (b, c) = 1. Then c|a Proof (ab, ac) =|a|(b, c) = |a|. But by hypothesis, one has c|ab, which implies that c|(ab, ac). We thus conclude that c|a. And the proof is complete. I am ...
0
votes
1answer
36 views

How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Theorem 1 If $a$ and $m$ are relatively prime integers and $m>1$, then an inverse of $a$ modulo $m$ ...
0
votes
1answer
32 views

To prove for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ , without Lucas' theorem

Can we prove by induction that for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ ? Or by some divisibility properties of Binomial co-efficients ? I wanted to ...
3
votes
4answers
49 views

Prove that if $na=mb$ and $(a,b)=1$, then $m=a$ and $n=b$.

I'm sorry but I'm having a massive brain fart. I'm trying to show that if $na=mb$ and $(a,b)=1$, with $a,b,n,m \in \mathbb{N}$ of course, then $m=a$ and $n=b$. Moving to $\mathbb{Q}_+$, we note that ...
0
votes
1answer
67 views

Formula of MIPS (million instructions per second)

Could you please help me to understand the mathematics behind MIPS rating formula? The performance of a CPU (processor) can be measured in MIPS. The formula for MIPS is: $$MIPS = \frac{Instruction \ ...
5
votes
3answers
107 views

Solve: $ab+bc+ca\mid (a+b+c)^2$

I couldn't make any progress on this problem, can anyone help? I found it's the same as: Find all integers $a,b,c$ such that $ab+bc+ca$ divides $a^2+b^2+c^2$. I found a solution $a=-b=1$, and $c$ ...
1
vote
1answer
17 views

If $n \in \mathbb Z^+$ , $a,b$ are integers such that $d=g.c.d.(a-b,n)$ , then $d^2|a^n-b^n$ ?

If $n \in \mathbb Z^+$ , $a,b$ are integers such that $d=g.c.d.(a-b,n)$ , then is it true that $d^2|a^n-b^n$ ?
0
votes
1answer
15 views

Find $a+b$ for $a, b$ such that $(x+1)^{n}(x^{2}+ax+b) \equiv 2^{n}(x-1) \mod (x-1)^{2}$

Since $2^{n} = \sum_{0}^{n}\binom{n}{k},$ we have from the given congruence the congruence $$\sum_{0}^{n}\binom{n}{k}(x^{k+2} + ax^{k+1} + bx^{k} - x +1) \equiv 0 \mod (x-1)^{2}.$$ The given answer ...