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

learn more… | top users | synonyms (1)

1
vote
0answers
9 views

Gaussian elimination algorithm performance

I am developing the quadratic sieve algorithm and I reached a new bottle neck: The matrix processing. I been reading quit a lot about this topic and I found many solutions Gaussian elimination: ...
-1
votes
1answer
39 views

Linear Combinations? [on hold]

Suppose $a$ is an integer such that $a$ divides $a_j$ for all $1 \le j \le n$. Show that $a$ divides any integer linear combination of $a_1, a_2, \ldots, a_n$.
0
votes
1answer
19 views

Prove that if $\gcd (a,n)=1$, $as=1 \pmod n$ has a solution

I can prove that if $\gcd (a,n)=1$, then $as=1 \pmod{n}$ has a solution. However, I cannot prove that the solution $s$ is in the set $\{1, 2, ..., n-1\}$.
-1
votes
1answer
48 views

Prove that $3|n ^{2} -1$ [on hold]

If $n$ is an integer such that $n\ge2$ and $3|n-1$, show that $3|n^{2}-1$.
-1
votes
0answers
22 views

Find the positive integers $\overline {abc}$ such that $\frac{1}{a} +\frac{1}{b}+\frac{1}{c}$=$\frac{\overline {1b}}{\overline {1a}}$ [on hold]

Find the positive integers $\overline {abc}$ such that $\frac{1}{a} +\frac{1}{b}+\frac{1}{c}$=$\frac{\overline {1b}}{\overline {1a}}$.Can you help me with one solution without to consider the ...
1
vote
0answers
17 views

Stern-Brocot Tree and sum of coefficients of continued fraction

Suppose we are given a continued fraction $$\frac{p}{q}=a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\frac{1}{a_{4}+\cdots}}}$$ I am trying to find an expression, possibly asymptotic, for the sum of the ...
2
votes
2answers
36 views

Given integers $x,\,y$ s.t. $x^2-16=y^3$, show that $x+4$ and $x-4$ are perfect cubes

Suppose $x$ and $y$ are some integers satisfying $$x^2-16=y^3.$$ I'm trying to show that $x+4$ and $x-4$ are both perfect cubes. I know that the greatest common divisor of $x+4$ and $x-4$ must divide ...
1
vote
0answers
20 views

What are the biggest possible number of equal values on this NxN box?

In a nXn box(n>3),a number is written on every cell such that the sums along all rows and columns are the same.Not all numbers are the same.What is the biggest possible number of equal values in the ...
0
votes
1answer
7 views

If $N = {q^k}{n^2}$ is an odd perfect number given in Eulerian form, does $\sigma(n^2)/q$ divide $2n^2 - \sigma(n^2)$?

Let $\sigma(x)$ be the sum of the divisors of $x$. A number $X$ is called perfect if $\sigma(X) = 2X$. Denote the abundancy index $\sigma(X)/X$ by $I(X)$. If $N$ is odd and perfect, then $N$ can be ...
2
votes
1answer
27 views

Integer (or whole) numbers in arbitrary fields.

Given an arbitrary field $K$, may I define an integer in $K$? I have found how to define an algebraic number in $K$ and how to define an integer algebraic number in $K$. For instance, let ...
0
votes
0answers
21 views

Can you show a proof of Unique Factorization of Integers Theorem (Fundamental Theorem of Arithmetic)?

I understand the proof of "Any integer greater than 1 is divisible by a prime number" by strong mathematical induction. But I don't understand why Unique Factorization of Integers Theorem follows ...
1
vote
0answers
42 views

Find $\sum_{i=1}^{2000}\gcd(i,2000)\cos\left(\frac{2\pi\ i}{2000}\right)$

What is the value of the following sum? $$\sum_{i=1}^{2000}\gcd(i,2000)\cos\left(\frac{2\pi\ i}{2000}\right)$$ where $\gcd$ is the greatest common divisor.
0
votes
1answer
37 views

Divisibility test for 720 [on hold]

Use the divisibility test where possible to list all factors of 720 Please show further examples where appropriate, thank you.
1
vote
1answer
23 views

$\mathbb N$ as the intersection of all inductive subsets of $\mathbb R$

I read in an undergraduate real analysis textbook that the set of the natural numbers $\mathbb N$ is defined as the intersection of all inductive subsets of $\mathbb R$. However, I'm having trouble ...
2
votes
2answers
48 views

Comparing a Factorial and a Perfect Power

Let us define the following recurrence relations as so. $$a_1=6, a_{n+1}=a_n!$$ $$b_1=6, b_{n+1}=6^{b_n}$$ So, which of the following is larger? $a_{b_2}$ or $b_{a_2}$? To clarify, I am trying to ...
1
vote
0answers
24 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 ...
1
vote
4answers
64 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
37 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
45 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
36 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
37 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 ...
0
votes
2answers
38 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
21 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
12 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
66 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
22 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
31 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
51 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$.
5
votes
1answer
119 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
60 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
28 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
39 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
39 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
31 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 ...
4
votes
1answer
29 views

Proving that the Calkin-Wilf tree enumerates the rationals.

The Calkin-Wilf tree is an infinite undirected graph (tree) which is constructed as follows: starting from the root at $\frac{1}{1}$, each node $\frac{a}{b}$ has two children: a left child ...
0
votes
3answers
49 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) - ...
0
votes
0answers
29 views
+50

Range of inverse harmonic mean of two integers

Today I was solving an exercise and one of the things I tried (which later turned out to be useless) involved considering the following: Is there a simple way to describe in terms of $n$ the range of ...
4
votes
5answers
155 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
93 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
3answers
414 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
0answers
36 views

On even almost perfect numbers other than the powers of two, as compared to odd perfect numbers given in Eulerian form

(Note: I have edited this question to conform to the further details added in the cross-post to MO.) Let $\sigma(x)$ be the sum of the divisors of $x$. We say that $X$ is almost perfect if ...
-2
votes
4answers
19 views

Collecting sufficient conditions for Sorli's conjecture on odd perfect numbers

(Note: This question has been cross-posted from MO.) Sorli's conjecture predicts that, for an odd perfect number $N$ given in the Eulerian form $N = {q^k}{n^2}$ (where $q$ is prime with $\gcd(q, n) ...
9
votes
6answers
214 views

Which of the numbers $300!$ and $100^{300}$ is greater

Determine which of the two numbers $300!$ and $100^{300}$ is greater. My attempt:Since numbers starting from $100$ to $300$ are all greater than $100$. But am not able to justify for numbers between ...
-2
votes
1answer
102 views

Equation involving floor function: [closed]

Given n a natural number, find $x$ (positive real number) such that: $$ 6\lfloor x \rfloor=n, $$ where $ \lfloor x \rfloor $ represents the value of the floor function in x.