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

learn more… | top users | synonyms (1)

0
votes
0answers
6 views

On the existence of magic squares of every order different from $2$

I was reading about magic squares and suppose that we speak here only of the magic squares that have in itself numbers from $1$ to $n^2$. It is easy to see that we cannot have $2$x$2$ magic square ...
3
votes
1answer
33 views

In $U(55)$ show $x \mapsto x^3$ is injective

I am stuck on showing that $\varphi : U(55) \to U(55) $ given by $x \mapsto x^3$ is an isomorphism. I already knwo that $\psi: U(n)\to U(n), \psi(x) = x^k$ is an isomorphism if and only if $\gcd(k,n) ...
1
vote
2answers
29 views

I don't understand a step in the proof of Euler's Theorem, please explain

I am trying to learn the proof for Euler's theorem which states: If $\gcd(a,m)=1$ then $a^{\phi(m)} \equiv 1 \mod m$. The proof goes like this. Take the reduced residue system modulo $m$. ...
1
vote
3answers
41 views

For which $n \in \mathbb{N}$ does $x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$ have at least $7$ distinct solutions?

I have to find one $n \in \mathbb{N}$ such that $$x^8 + [2]_nx^7+[6]_nx^6-x^2-[2]_nx - [6]_n = [0]_n$$ has at least $7$ distinct solutions in $\mathbb{Z}_n$ (or, equivalently, $f(x) = x^8 + ...
5
votes
1answer
39 views

How to prove this curiosity that has to do with cubes of certain numbers?

I saw on facebook some image on which these identities that I am going to write below are labeled as "amazing math fact" and on the image there are these identities: $1^3+5^3+3^3=153$ ...
1
vote
1answer
33 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
0
votes
0answers
26 views

How to square a number that got more digits than search results “digits” on Google.

I am implementing the quadratic sieve algorithm. And I got run in unexpected problem. Take a look at those two final steps of the algorithm as described in wiki. Use linear algebra to find a ...
1
vote
1answer
11 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
votes
0answers
41 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
25 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
2answers
40 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, ...
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
21 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
51 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$.
-3
votes
0answers
46 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
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 ...
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 ...
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.
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.
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 ...
1
vote
0answers
27 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
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 ...
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)
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 ...
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 ...
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
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 ...
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
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$. ...
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
23 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 ...
3
votes
3answers
70 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
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 ...
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
40 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
57 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 ...