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

learn more… | top users | synonyms (1)

1
vote
1answer
10 views

Sums of remainders in Euclidean GCD algorithm

I've noticed that when going through the steps of Euclidean GCD algorithms, very often the sum of the remainders in the steps $s_{i+1}$ and $s_{i+2}$ will be equal to the remainder in step $s_i$. ...
1
vote
2answers
23 views

When the Sum of digits exceed the Number of Divisors

Could somebody help me prove that there are a infinite number of natural numbers for which their sum of digits exceeds the number of divisors? If $S(n)$ denoted the sum of digits, and $\sigma_k(n)$ ...
1
vote
1answer
152 views

Quadratic Reciprocity - Legendre Symbols

Find the value of $(\frac{1\cdot 2}{73})+(\frac{2\cdot 3}{73})+...+(\frac{71\cdot 72}{73})$. This is based off each fraction being a Legendre Symbol. I tried to find a pattern... but I could't find ...
-3
votes
0answers
44 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 a solution without to consider the case ...
-1
votes
0answers
39 views

Find $a,b,c \in \{1,2,..,9\}$ such that $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{10+a}{10+b}$ [on hold]

Find $a,b,c \in \{1,2,..,9\}$ such that $$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{10+a}{10+b}.$$ It seems to be easy but I want a smart solution.
1
vote
2answers
38 views

$x^4 - y^4 = 2z^2$ intermediate step in proof

I am ultimately trying to prove, for an Exercise in Burton's Elementary Number Theory, that $x^4 - y^4 = 2z^2$ has no solution in the positive integers. I can establish that if there is a solution, ...
0
votes
1answer
41 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 ...
0
votes
3answers
56 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 ...
3
votes
3answers
41 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 ...
2
votes
0answers
31 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
40 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
20 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\}$.
8
votes
0answers
268 views

A question on odd perfect numbers

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$. If $\sigma(M) = 2M$, then $M$ is said to be perfect. Currently, there are $48$ known examples of even perfect numbers -- on ...
2
votes
4answers
63 views

the product of an odd perfect number and some even perfect number is perfect

If $a$ were an odd perfect number ,does there exist an even perfect number $b$ such that $ab$ is a perfect number?
7
votes
1answer
391 views

What is the period of this sequence?

Consider the recurrence relation: $$x_{i+1}=p-1-((p \cdot i-1) \mod{x_i})$$ If $p$ is prime and $x_0=1$, what is the least period of the resulting (eventually periodic) sequence? My guess is the ...
-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) ...
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 ...
-1
votes
1answer
50 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
vote
0answers
18 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
40 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 ...
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 ...
25
votes
6answers
538 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 ...
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 ...
2
votes
2answers
103 views

Prove that $f(n)$ is the nearest integer to $\frac12(1+\sqrt2)^{n+1}$?

Let $f(n)$ denote the number of sequences $a_1, a_2, \ldots, a_n$ that can be constructed where each $a_i$ is $+1$, $-1$, or $0$. Note that no two consecutive terms can be $+1$, and no two ...
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
32 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 ...
2
votes
4answers
1k views

Last digits number theory. $7^{9999}$?

i have looked at/practiced several methods for solving ex: $7^{9999}$. i have looked at techniques using a)modulas/congruence b) binomial theorem c) totient/congruence d) cyclicity. my actual desire ...
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
4answers
67 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 ...
2
votes
0answers
47 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.
3
votes
5answers
90 views

What will be the remainder when $2^{31}$ is divided by $5$?

The question is given in the title- Find the remainder when $2^{31}$ is divided by $5$. My friend explained me this way- $2^2$ gives $-1$ remainder. So,any power of $2^2$ will give $-1$ ...
0
votes
1answer
106 views

Poincare series

I understand the concepts used in the Poincaré series, but I don't know how to compute the Poincaré series of a specific polynomial, for example $x^2-a$, what must I do?
0
votes
1answer
38 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.
0
votes
0answers
37 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
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.
1
vote
1answer
25 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
50 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 ...
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 ...
1
vote
0answers
26 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 ...
3
votes
3answers
39 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 ...
1
vote
1answer
38 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)
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
416 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
2answers
39 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
25 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 ...
0
votes
0answers
22 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 ...
2
votes
1answer
67 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$. ...
3
votes
1answer
47 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 ...
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 ...