Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

0
votes
0answers
17 views

Criteria for inequality

I am working with an inequality and I need to prove something of the shape $$c\cdot a+d\cdot b \leq a\cdot b$$ The numbers $a$ and $b$ have a specific form, but for the $c$ and $d$ I only know that ...
0
votes
4answers
44 views

If $a > 0$,$b>0$, and $\frac{1}{a} + \frac{1}{b}$ is an integer, prove that $a=b$. And show that $a = 1$ or $2$

If $a$ and $b$ are positive integers, and $\frac{1}{a} + \frac{1}{b}$ is an integer, prove that $a=b$. And show that $a = 1$ or $2$ -I played around with numbers and the conditions and it seems that ...
1
vote
1answer
29 views

If $m | (8n +7)$, $m | (6n + 5)$, prove that $m = ± 1$

If $m | (8n + 7)$, $m | (6n + 5)$,prove that $m = ± 1$ -We have just starting going over the "divides" notation, and I am aware of a few properties and theorems from my notes. I am; although, a bit ...
1
vote
1answer
39 views

Why is the gap between consecutive twin primes always a number of integers divisible by 3?

For example: (5,6,7)8,9,10(11,12,13) (227,228,229)230,231,232,233,234,236,237,238(239,240,241)
2
votes
3answers
33 views

If $\gcd(a, c) = 1$ and $b | c$, prove that $(a, b) = 1$

If $\gcd(a, c) = 1$ and $b \mid c$, prove that $(a, b) = 1$ -Not sure how to approach this problem. -We have just started the greatest common divisor section, and looking at my notes I see that ...
3
votes
3answers
28 views

If a is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$

If a is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$ -We have just started the section on greatest common divisor, one thing I know is that $gcd(a,b) = ax + by$ -My initial thought is that we ...
-1
votes
0answers
21 views

Finding the number of positive divisors [on hold]

Let $x=2^33^2$. Find the number of positive divisors of $x^2$ that is greater than $x.$
0
votes
2answers
32 views

Solve the following congruence: $x(x+1)(x+2) \equiv 0 \pmod{221}$

Find the first five solutions for, $$x(x+1)(x+2) \equiv 0 \pmod{221}$$ I am very confused. By CRT, $x(x+1)(x+2) \equiv 0 \pmod{13}$ and $x(x+1)(x+2) \equiv 0 \pmod{17}$ But these two ...
0
votes
0answers
17 views

What does $(a_i,m)=1$ mean in number theory?

I believe it means the greatest common divisor of $a_i$ and $m$ is $1$, meaning $a_i$ and $m$ are co-prime, but I want to be sure. Here is the context: A reduced residue system modulo $m$ is a set ...
1
vote
1answer
10 views

order of a subrgoup of rank $r\geq 2$ in $\mathbb{F}_p^*$

Let $a,b\in \mathbb{F}_p^*$ with orders $o_p(a)=|\langle a \rangle|=\alpha$ and $o_p(b)=|\langle b \rangle|=\beta$. I have few questions: 1) Is it true in this case ($\mathbb{F}_p^*$ cyclic) that ...
2
votes
1answer
64 views

Solving $x^2 \equiv -x\pmod{2015}$

Problem: Find all integer solutions of $x^2 \equiv -x \pmod{2015}$. I proceeded this way: first, I realized that $2015 = 5 \times 13 \times 31$. I rewrote $x^2 \equiv -x$ as $x^2 + x \equiv 0$. ...
0
votes
0answers
22 views

How can I define $H+K$? [duplicate]

Let be integers 5 and 100, and let be $H=5Z$ and $K=100Z$ subgroups of the additive group $Z$. How can I define the subgroup $H+K$ ? I think $5Z+100Z=5Z$ because mcd(100,5)=5 but I'm not sure that ...
0
votes
1answer
21 views

If P(i) is true for all integers i with 2≤i≤k as inductive hypothesis, then why also p(t) is true by the inductive hypothesis?

"Let P(n) be the property n is divisible by a prime number. We prove that P(n) is true for all integers n with n> 1. Basis step. If n=2, then P(n) is true because 2 is a prime and every ...
1
vote
1answer
29 views

How does the fact that Fermat primes are relatively prime imply there are infinite primes?

I was just reading a book called Proofs from the Book. It presented the proof given by George Polya to prove that two Fermat primes (numbers of the form $2^{2^n} + 1$) are always relatively prime, ...
0
votes
2answers
45 views

A number theory contest problem

I have come across a problem I can't solve. Can anyone help? Here is the problem Find least integer $N$ such that sum of the digits of both $N$ and $N+1$ is divisible by $7$.
4
votes
1answer
96 views

Is it possible to find a perfect cube like 111…11?

Can we find a perfect cube like $111...111$(all digits are $1$), apart from the number $1$ itself? It's easy to prove that there can't be anything like $111...11$ that is a perfect square besides ...
2
votes
2answers
58 views

How can I prove that only there continuous odd prime are $3,5,7$?

How can I prove that the only prime number $p$, such that $ p,p+2,p+4$ are primes is 3?
1
vote
3answers
38 views

Proof of divisibility: $17 \mid 3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ [on hold]

As the title says, prove that $3 \cdot 5^{2015} + 2^{2017} \cdot 5^{670}$ is divisible by $17$.
2
votes
2answers
34 views

Calculate $\sqrt{x^2+y^2+2x-4y+5} + \sqrt{x^2+y^2-6x+8y+25}$, if $3x+2y-1=0$

As the title says, given $x,y \in \mathbb{R}$ where $3x+2y-1=0$ and $x \in [-1, 3]$, calculate $A = \sqrt{x^2+y^2+2x-4y+5} + \sqrt{x^2+y^2-6x+8y+25}$. I tried using the given condition to reduce the ...
2
votes
2answers
23 views

Divisibility: $60 \mid (2x-y)(2y-z)(3z+2x)$, if $8x-10y+27z=0$

As the title says, given $x,y,z \in \mathbb{Z}$, where $8x-10y+27z=0$, prove that $(2x-y)(2y-z)(3z+2x)$ is divisible by $60$. I tried to bring the formula in a format of $(\cdots)(8x-10y+27z) + ...
0
votes
1answer
38 views

Find $n$ such that $209$ divides $n^{180}-n^{20}-n^{36}+1$

Finding $n\in \mathbb{N}$ (with $n > 1$) such that $209$ divides $n^{180}-n^{20}-n^{36}+1$ is equivalent to solving $$ n^{180} - n^{20} - n^{36} + 1 \equiv 0 \mod 11 \quad \text{ and } \quad ...
2
votes
1answer
26 views

Find all elements of multiplicative order 18.

Find all elements of $\mathbb{Z}_{19}^*$ of multiplicative order $18$. I started by using Euler's Theorem and since gcd(18, 19) = 1 it implies that $a^{\phi (19)} \equiv 1 \pmod n$. Which means ...
2
votes
2answers
37 views

Is there an easy way to check whether or not $3$ divides a number that is written in decimal notation?

(Convention. I include $0$ in the natural numbers, i.e. $0 \in \mathbb{N}$) Definition. Whenever $n$ is a natural number, define that $$\langle n\rangle : \{0,\ldots,9\}^\mathbb{N}$$ is the unique ...
0
votes
1answer
38 views

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
0
votes
3answers
41 views

Variation on Fermat Little Theorem

Does the following variation of Fermat Little Theorem hold? How do you prove it? Let $p$ be a prime number greater than $3$. Then there exist a natural non-prime $m > 1$ such that ...
0
votes
1answer
29 views

How many $3$-digit positive integers can be represented as the sum of exactly nine different powers of $2$?

How many $3$-digit positive integers can be represented as the sum of exactly nine different powers of $2$? What does this question mean? Is the sum of $9$ different powers of $2$ like ...
2
votes
2answers
73 views

Proof of $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$

Prove that $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$ Card $\mathbb{N}^\mathbb{N} = \aleph_0^{\aleph_0}$ Card $(0, 1) = \mathbb{c}$ Define: $f: ...
0
votes
3answers
44 views

Find the value of y in $11y \equiv 14 \pmod{19}$

Find the value of $y$ in $11y \equiv 14 \pmod{19}$. My issue is not with finding a solution. Using the Euclidean algorithm and Bezout's identity I get a final expression of: $$(11)(7)(14) - ...
1
vote
1answer
25 views

Prove that if $17 \not\mid n$, then either $17 \mid n^8+1$ or $17 \mid n^8-1$

Question is : Let $n$ be a natural number not divisible by $17$. Prove that either $n^8+1$ or $n^8-1$ is divisible by $17$. I tried to solve using Fermat theorem for a prime number $p$, and any ...
0
votes
0answers
58 views

The condition that given polynomial is divisible by 3

In How can I prove that the following is divisible by 3?, I showed $k^3+3k^2+2k$ is divisible by $3$ using Euler's theorem, specifically, Fermat's little theorem. Then I thought that it is possible to ...
4
votes
5answers
152 views

Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.) Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for ...
5
votes
3answers
92 views

The only positive integers that divide successive numbers of the form $n^2+3$ are $1$ and $13$

I stuck with this problem, I don't know how to start with. Prove that the only positive integers that can divide successive numbers of the form $n^2+3$ are 1 or 13.
1
vote
4answers
394 views

Why is the Axiom of Infinity necessary?

I am having trouble seeing why the Axiom of Infinity is necessary to construct an infinite set. According to a professor of who's mine teaching a class on "infinity," the Peano axioms are only ...
0
votes
3answers
61 views

Minimizing the difference between two prime numbers [closed]

I tried to somehow simplify the statement to find $(q-p)$ but I couldn't. Here is the question: Given that $p$ and $q$ are prime numbers with $p<q$ and given that $pq-p-q = 59$, what is the ...
1
vote
0answers
75 views

Why is proving that $10$ is solitary considered very difficult?

The title says it all. We denote the sum of the divisors of $x$ by $\sigma(x)$. The ratio $I(x)=\sigma(x)/x$ is called the abundancy index of $x$. If $I(m)=I(n)$, then $\{m,n\}$ is called a ...
0
votes
0answers
24 views

Can distinct odd perfect numbers $N = {p^k}{m^2}$ share the same Euler factor $p^k$?

(A similar question has been asked in MO.) Let $\sigma(x)$ denote the sum of the divisors of $x$, and call the ratio $I(x) = \sigma(x)/x$ as the abundancy index of $x$. A number $N$ is called ...
23
votes
6answers
511 views

What would Gauss do in this case: adding $1+\frac12+\frac13+\frac14+ \dots +\frac1{100}$?

We all know the story related to Gauss that Gauss' class was asked to find the sum of the numbers from $1$ to $100$ as a "busy work" problem and and he came up with $5050$ in less than a minute. He ...
3
votes
1answer
46 views

A relation related with odd perfect numbers

It is easy to prove, using the relation $\prod_{d\mid n}d=n^{\sigma_0(n)/2}$ holds for $n\geq 1$ where $\sigma_0(n)$ is the number of divisors, the following Proposition. The integer $n\geq 1$ is ...
2
votes
2answers
95 views

Proving $2^{2^n}+3^{2^n}+5^{2^n}$ is divisible by $19$ for all $n\geq 1$ by induction

I came across the following in the book Handbook of Mathematical Induction: $$ 19\mid (2^{2^n}+3^{2^n}+5^{2^n}),\quad n\in\mathbb{Z^+}\tag{1} $$ Apparently, this problem is not so bad if you think ...
1
vote
0answers
75 views

Reasoning about prime counting and the twin prime conjecture

I've been thinking the primorial for say the $i$th prime $p_i$and the equations for counting the number of elements in the reduced residue system for this primorial and counting the number of elements ...
3
votes
4answers
73 views

Prove that $(n^2-1)\mid(n^3+1)$ iff $n=2$

Seperating $n^2-1$ into $(n+1)(n-1)$. I have noticed that $n^3+1=(n+1)(n^2-n+1)$, so we have $\forall n\geq 2$, $(n+1)\mid(n^3+1)$. We now need to show that $(n-1)\mid(n^2-n+1)$ iff $n=2$ This ...
0
votes
0answers
37 views

Modular Division and Factorial

I am unfamiliar with number theory but am trying to calculate the following for a coding challenge: $$\frac{(N-M-1)!}{N!(M-1)!}\pmod{Q}$$ where $Q$ is prime. I know that I can calculate the ...
64
votes
12answers
8k views

Is there something special about 2015? [closed]

Is there some property which is satisfied only by the number 2015 (among natural numbers, say) or is there a relatively simple question for which the answer is, surprisingly, 2015? This is inspired ...
71
votes
11answers
13k views

Am I just not smart enough? [closed]

When I was doing math, let us say for example, introductory number theory, it seems to take me a lot of time to fully understand a theorem. By understanding, I mean, both intuitively and also ...
52
votes
4answers
3k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
2
votes
1answer
143 views

Estimate or calculate the number of digits of a multiplication

I would like to calculate the number of digits of these multiplications 2 x 4 200 x 300 2 (12321) (1000). I don't exactly know how to start. Of course I know that I can multiply the numbers and ...
7
votes
1answer
4k views

What is a residue class?

My number theory book has hopelessly lost me on the topic of residue classes. I understand the very basics of congruence and modular arithmetic, but if someone could give not only a formal, but ...
13
votes
17answers
10k views

How to Prove the divisibility rule for $3$

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large ...
51
votes
9answers
4k views

The last digit of $2^{2006}$

My 13 year old son was asked this question in a maths challenge. He correctly guessed 4 on the assumption that the answer was likely to be the last digit of $2^6$. However is there a better ...
20
votes
8answers
2k views

Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...