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

learn more… | top users | synonyms (1)

2
votes
2answers
232 views

Second Course in Number Theory - Self Study

I just finished a first course in number theory using Dudley's Elementary Number Theory. This was by far my favorite math course and I want to learn more number theory this summer. As far as ...
3
votes
0answers
172 views

Conjecture on OEIS A167055

OEIS A167055 Numbers n such that $12n + 5$ is prime. $0, 1, 2, 3, 4, 7, 8, 9, 11, 12, 14, 16, 19, 21,...$ are items of OEIS A167055. I conjecture that the set of the sum of every two items of this ...
0
votes
1answer
53 views

Verify my proof on elementary number theory

I've tried to prove this theorem, which is very simple, but is a kind of practice for me. Let $a,b$ be two positive integers. Therefore, if $a+b$ is a composite number, $frac(\frac{a}{l}) + ...
0
votes
3answers
54 views

Equation involving power of two

I want to show that the equation $2^x - 1 = 3^y$ does not have any positive integer solutions except for $ x = 2 , y = 1$ . Is it possible to prove the assertion using binary representation of powers ...
1
vote
0answers
276 views

Vieta jumping with non-monic polynomials

I have recently discovered Vieta jumping as a problem-solving technique. In order to teach myself about it, I have located most (all of?) the standard references, both here on MSE and "out there" (via ...
1
vote
1answer
40 views

Polynomial that is surjective $\mod n$ for all $n$?

I was curious about an existence of the following polynomial $f(x) \in \mathbb{Z}[x]$ and $f(x) \not = x$ such that given any $n \in \mathbb{N}$, $f: \mathbb{Z} / n\mathbb{Z} \rightarrow \mathbb{Z} / ...
3
votes
2answers
171 views

How to show that $\displaystyle [a,b,c] = \frac{abc}{(ab,bc,ca)}$ without prime factorization?

I think this has been asked before, but I couldn't find it on math.SE. I googled it too, but I wasn't lucky enough to find it there either. So, here's the problem: Demonstrate that for any $a,b,c \in ...
1
vote
3answers
136 views

Help needed in understanding proof: Every odd prime $p$ has exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues.

Help needed in understanding proof: Every odd prime $p$ has exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. We assume there exist $k$ incongruent quadratic residues and ...
1
vote
2answers
113 views

Hard elementary-number-theory question on solve all $n$s that make $2^6+2^{10}+2^n$ a square numbe

I want to know all the nonnegative integer $n$ that makes $2^6+2^{10}+2^n$ be some other integer's square. I have tried it numerically for a range from $0$ to $1000$, and only $0,9,11,12,15$ returns ...
6
votes
4answers
248 views

Tell whether $\dfrac{10^{91}-1}{9}$ is prime or not?

I really have no idea how to start. The only theorem considering prime numbers I know of is Fermat's little theorem and maybe its related with binomial theorem. Any help will be appreciated.
3
votes
2answers
111 views

Number of algebraic integer divisors of an algebraic integer

Let $\alpha$ be an algebraic integer of degree $d$. Let $\tau(\alpha)$ be the number algebraic integers $\beta$ of degree $d$ such that $\alpha/\beta \in \mathbb{Z}$. What is a good upper bound on ...
1
vote
0answers
70 views

The elegant expression in terms of gcd and lcm - algebra - (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to ...
2
votes
1answer
57 views

The elegant expression in terms of gcd and lcm - algebra

Given three positive integer numbers $k_1$, $k_2$, $k_3$, we may denote their greatest common divisor(gcd) by $\gcd(k_i,k_j)\equiv k_{ij}$ for gcd of a two pair of number $k_i,k_j$. ...
2
votes
1answer
44 views

Prove that $n=a^2+b^2-c^2$. [duplicate]

For any natural number $n$ prove that there exist natural numbers $a,b,c$ for which $$n=a^2+b^2-c^2.$$ I think we can have a proof by induction because : If $n=0$ we choose $a=b=c=0$ or $a=0,b=c$. ...
1
vote
1answer
138 views

Bezout's lemma in Euclidean Domains

I'm wanting to show that given an ED $R$ whose identity is $1$, and two elements $a, b \in R$ whose gcd is a unit, that $\exists x, y \in R $ st $ax + by = 1$. Caveat-- I don't want to utilize the ...
1
vote
0answers
84 views

About a paper by Gold & Tucker (characterizing twin primes)

I've carefully looked at the questions on prime and twin prime, but the following question seems not to habe been asked before. Context: In the paper by Jeffrey F. Gold and Don H. Tucker titled A ...
1
vote
3answers
37 views

Why is $a^c-1$ composite if $a>2$ or if $c$ is composite?

Here is the original theorem from my book (A Course in Number Theory by H.E.Rose, 2nd edition): Let $a>1$ and $c>1$ be integers. The integer $a^c-1$ is composite if $a>2$ or if $c$ is ...
1
vote
1answer
104 views

Number of unique products of two integers of bounded size

If $S,T$ are two sets of integers, define $S*T$ to be the set $S*T = \{st \mid s \in S, t \in T\}$. Let $[1,n]$ denote the set of integers in the range from $1$ to $n$, i.e., $[1,n] = ...
16
votes
1answer
214 views

How to sum this infinite series

How to sum this series: $$\frac{1}{1}+\frac{1}{11}+\frac{1}{111}+\frac{1}{1111}+\cdots$$ My attempt: Multiply and divide the series by $9$ ...
0
votes
0answers
97 views

Sum of the jumbled digits of $abc_{10}$ is $3194$

In the book that I am reading, the author denotes $abc_{10}$ as $100a+10b+c$ where $a, b, c \lt 10$. So if $a = 3$, $b=2$ and $c=8$ then $abc_{10} = 328$. The author asks the following problem: In ...
7
votes
4answers
301 views

Direct proof that $n!$ divides $(n+1)(n+2)\cdots(2n)$

I've recently run across a false direct proof that $n!$ divides $(n+1)(n+2)\cdots (2n)$ here on math.stackexchange. The proof is here prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer (it ...
2
votes
2answers
119 views

Proving $\prod_{i=1}^np_i+1$ is not a perfect square

Let $m=\displaystyle{\prod_{i=1}^np_n}$ be the product of the first $n$ primes $(n>1)$. prove that $m+1$ cannot be a perfect square. I think that the opposite it correct: $m+1$ is not a ...
0
votes
2answers
74 views

Freshman's Dream for Composite Characteristic

It is easy to see that if $p$ is prime, then $p$ divides the binomial coefficient $\binom p k$ when $1\leq k\leq p-1$. I am guessing that this fails for all composite integers, but I'm not quite sure ...
0
votes
2answers
25 views

Using two equations, creating a single equation with the same solutions as the original two?

I am a little confused about the notion of creating a single equation (from two other ones) which has the solutions of both other equations. For example, let my two equations be $u=v$ and $x=y$. A ...
23
votes
3answers
2k views

Fibonacci numbers that are powers of 2

Are there infinitely many Fibonacci numbers that are also powers of 2? If not, which is the largest?
2
votes
1answer
76 views

Prove this simple arithmetic relation

Prove that if $$a \mid b$$ and $$a \mid c$$ then $$a \mid bx+cy$$ for any integers $x$ and $y$. Here's my proof: $$b = ak$$ $$c = am$$ $$bx+cy = akx+amy = a(kx+my)$$ Notice that $kx+my$ is an ...
4
votes
2answers
114 views

Question on gcd, is this true?

Let $a,b \in \mathbb{Z^+},\ a<b,\ d=\gcd(a,b)\ $ and $\ 1<d<a,\ x=\frac ad,\ y=\frac bd,\ x,y \in \mathbb{Z^+}.$ Suppose $a=a_1+a_2,\ b=b_1+b_2,\ a_1<b_1,\ d_1=\gcd(a_1,b_1)$ and ...
1
vote
2answers
63 views

How to show that $x^2 \equiv 10 \bmod {101}$ does or does not have a solution

I know that this is solvable using index arithmetic, but that would take forever to generate the index table. How do I show that this does or does not have a solution without trying to solve it?
4
votes
1answer
71 views

Primes in an Infinite Set

Let $S$ be the infinite set of positive integers whose members can be written with no digits except $0$ and $1$ and with no more than $1988$ $1s$. Show that some integer $n$ does not divide any member ...
3
votes
2answers
57 views

Assume that $p$ is a prime, $a$ and $b$ are integers such that $p \mid b$ and $am+b=1$.

Assume that $p$ is a prime, $a$ and $b$ are integers such that $p \mid b$ and $am+b=1$. Prove that $x \equiv m(1+b+b^2+...+b^{k-1} \bmod {p^k}$ is the solution to $ax\equiv 1 \bmod{p^k}$. So I got ...
0
votes
3answers
61 views

Find values of $n$ that yield a prime number

Let $n$ be a positive integer, and $\frac{n(n+1)}{2}-1$ is a prime number. Find all possible values of n. What I have so far is this: $$\frac{n(n+1)}{2}-1=2, n=2$$ Also, $n^2+n-2\over2$ can be ...
2
votes
1answer
76 views

Prove that there are infinitely many relatively prime solutions of $x^2+y^2=z^3$

Show that for all integers k, there is a solution with $x=3k^2-1$ and $z=k^2+1$ You will need to calculate $y$ to show that there is such a solution, and show that the solution $(x,y,z)$ is ...
0
votes
1answer
38 views

How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a ...
5
votes
1answer
70 views

Let $a_1, \ldots,\ a_{100}$ be $100$ positive integers. Show that for some $m,\ n$ with $1\le m\le n\le 100, \sum_{i=m}^n a_i$ is divisible by $100$.

Let $a_1,\ a_2,\ a_3, \ldots,\ a_{100}$ be $100$ positive integers. Show that for some $m,\ n$ with $1\le m\le n\le 100, \sum_{i=m}^n a_i$ is divisible by $100$.
4
votes
0answers
81 views

A polynomial $\ f(x)$ has integer coefficients such that $\ f(0)$ and $\ f(1)$ are both odd numbers. Prove that $\ f(x) = 0$ has no integer solutions. [duplicate]

Let there be a polynomial $\ f(x)$. It has integer coefficients such that $\ f(0)$ and $\ f(1)$ are both odd numbers. Prove that $\ f(x) = 0$ has no integer solutions.
7
votes
3answers
129 views

Solving a congruence $x^{17} \equiv 243 \pmod{257}$

I'm trying to solve the following congruence: $x^{17} \equiv 243 \pmod{257}$ I have worked out that the $\gcd(243,257)=1$ and that $243=3^5$ So $x^{17} \equiv 3^5 \pmod{257}$ and I don't really ...
2
votes
1answer
50 views

Expressing $2^n$ as sum of five rational cubes

For which positive integers $n$ can $2^n$ be written as a sum of five non-zero rational cubes ? For which positive integers $n$ can $2^n$ be written as a sum of five positive rational cubes ?
1
vote
2answers
47 views

Number of primitive roots $\pmod{m}$

I'm trying to find the number of primitive roots $\text{mod} 1300$ I thought this was calculated using $\phi (\phi (m))$ but I get that there are $128$ primitive roots, where as the solutions say ...
1
vote
2answers
65 views

Number theory problems.

It is given: $3m+1=$perfect square. Express $m+1$, as the sum of $3$ perfect squares. I tried to solve the problem by checking for odd and even values perfect squares $4k^2,{(2k+1)}^2$. I got ...
0
votes
1answer
71 views

Number Theory Divisibility Question

(From Math Challenge II Number Theory packet) Given that $a,b,n$ are positive integers. Assume that for any positive integer $k\neq b, (k-b)\mid(k^n-a)$, the which of the following must be true? ...
0
votes
2answers
68 views

Direct proof that the product of odd integers is odd

Prove $P(x,y)$: If $x$ and $y$ are odd integers, then the product $xy$ must also be odd. I need a direct proof of this. I know that $ x $ and $y$ both have to equal to $2n+1$ in order for them ...
4
votes
1answer
78 views

Closed formula for a multiple Dirichlet convolution of the 1-function with the identity

For two multiplicative arithmetic functions $f,g$ the Dirichlet convolution is defined by $(f\ast g) (n)=\sum\limits_{ab=n}f(a)g(b)$. Convoluting any arithmetic function with the $1$-function ...
1
vote
2answers
377 views

Expressing an integer as the sum of three squares

I'm trying to determine if 1317 and 116 can be written as the sum of three squares? I have the condition that if it is not of the form $4^{\alpha}(8k+7)$ then it can be written as a sum of three ...
1
vote
0answers
350 views

Find primitive root mod 17

I have to list the quadratic residues of $17$ and find a primitive root. I have calculated that: Quadratic residues $mod(17)$ are $1,2,4,8,9,13,15,16$ How am I then meant to use this to obtain a ...
5
votes
4answers
272 views

Is there a conjecture with maximal prime gaps

Define $M_n$ to be the $n$th maximal gap between primes. That is, $M_1=1$ thanks to $3-2=1$; $M_2=2$ thanks to $5-3=2$; $M_3=4$ thanks to $11-7=4$; and in general, $M_n = p_{i+1}-p_i$, where $p_i$ is ...
0
votes
1answer
28 views

Find all values of parameter A such that two system of congruences are equal

I'm starting to learn some elementary number theory and i came across a task i don't know how to solve. $$x \equiv 5 (mod \ 6)$$ $$x \equiv A (mod \ 35)$$ and the second one $$x \equiv A (mod \ ...
3
votes
3answers
205 views

Finding remainder on division by 2014

I'm trying to find the remainder when $6^{936}$ is divided by $2014$ I started thinking I could use Euler's theorem but then noticed that $6$ isn't prime, I then tried to split it into $6=2 \times 3$ ...
2
votes
5answers
156 views

How much zeros has the number $1000!$ at the end?

I know that it depends of the factors of five and two. But the number is too long to figure how much factos of five and two there are. Any hints?
1
vote
0answers
185 views

solving congruence equation system modulo prime

I need to solve a congruence system like this: $30f_0+26f_1+8f_2+38f_3+2f_4+40f_5+20f_6 \equiv 0 \pmod{41}$ $38f_0+2f_1+40f_2+20f_3+30f_4+26f_5+8f_6 \equiv 0 \pmod{41}$ ...
2
votes
2answers
80 views

Proof of Lucas' Theorem: Help in understanding contradiction

I've tried understanding the below theorem by Lucas. The proof is by contradiction, but I don't see why there is a contradiction in $$(x^e)^{(k/q)} \equiv 1 (\mod n)$$ ? Also is the theorem valid for ...