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

learn more… | top users | synonyms

0
votes
2answers
49 views

Can Euclid's Division Algorithm and/or Fundamental Theorem of Arithmetic implies this property of prime numbers

There is an exercise on page 44 of Amann's book Analysis, Vol I which stuck me so much. I quoted it here: Ex7: Let $p\in\mathbb{N}$ with $p>1.$ Prove that $p$ is a prime number if and only if, ...
0
votes
1answer
20 views

Periodicity in modulos of the form $10^k$

Several months ago, I found a statement on the web that the modulus $10^k$ has a period of $$\text{lcm}(\Phi(2^k),\Phi(5^k))$$ where $\Phi$ is the euler totient function. In other words, if $$p ...
1
vote
2answers
74 views

How to prove $~(c - b) ^ 2 + 3cb = x^3~$ has no nonzero integer solutions?

I'm trying solve: $~a^3 + b^3 = c^3~$ has no nonzero integer solutions. Only one problem left: because $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = a ^ 3,\quad (1)$ if $~c-b~$ is a cubic number, ...
6
votes
0answers
78 views

When is $(x^n-1)/(x-1)$ a prime number?

Let $x > 1$ and let $n$ be a prime. I'm wondering if a characterization of this is known. That is, what are sufficient and necessary conditions for $$ \dfrac{x^n-1}{x-1} = 1 + x + x^2 + \cdots + ...
0
votes
2answers
67 views

Prove that $(2n+1)+(2n+3)+\dots +(4n-1) = 3n^2$ by induction

Note: This is for self study, the book is Elementary analysis by Kenneth. A. Ross How to prove the following by mathematical induction, I am stuck
0
votes
0answers
26 views

How to prove the maximum and the minimum of the set of divisors of $a\in \mathbb{Z}$

Let $a$ be a non-zero integer. We define the set of divisors of $a$, $D(a)$, as follows: $D(a) = \{ n \in \mathbb{Z} | n \text{ divides } a\}$ So, the minimum element of $D(a)$ is $-|a|$, ...
1
vote
1answer
35 views

This a gcd question about a particular algebraic expression. [duplicate]

How does one show that: if $\gcd( x, y) = 1$, then $\gcd( x+y, x^2 - xy + y^2) = 1\,{\rm or }\,3$.
0
votes
0answers
51 views

Why $0^0$ is not equal to $1$? [duplicate]

Suppose that 0^0= x Then, taking logarithm in both side we got: 0*log 0= log x Left hand side is equal to 0, so: 0= log x Then, the satisfied value of x is only 1. So, 0^0= 1 But, in calculus ...
6
votes
1answer
51 views

Torsion of finitely generated $\mathbb Z_ \ell$-module finite?

Let $M$ be a finitely generated $\mathbb Z_ \ell$-module, where $\ell$ is a prime number and $\mathbb Z_\ell$ is the ring of $\ell$-adic integers. Let $T$ be its torsion submodule. Is $T$ finite? In ...
0
votes
1answer
24 views

Check my proof : gcd(a,b)=1=gcd(x,y) => (xa,yb)=gcd(x,b) gcd(y,a)

Note: (x,y) means gcd(x,y) I managed to prove the next Proposition: Let $(a,b)=1=(x,y)$. Then $(x a,y b)=(x,b)(y,a)$. It can be easily be generalized for the case that $(a,b)\neq1$ and or ...
0
votes
4answers
85 views

Find a pair of integers $n,x$ such that $84 = nx + (n-1)n$ and $x$ is odd

I have a equation like this: $$84 = nx + (n-1)n$$ where, $x$ is odd. I need to find the fastest way to find a possible $n$ and $x$. (In this case: $n = 6, x = 9$) Edit: Maybe the background ...
1
vote
0answers
43 views

Similarity of two limits related to the sum of divisors $\sigma(n)$ and the harmonic numbers $H_n$

Given that the sum of divisors has the form: $$\large \sigma(n) = \sum _{k=1}^n \lim_{s\to 0} \, \left(\frac{(s+1) (-1)^{\frac{2 n}{k}}+s-1}{k \cdot s \cdot 2}\right)^{-1}$$ $$1, 3, 4, 7, 6, 12, 8, ...
0
votes
1answer
47 views

Does every number has a multiple of it which is equal to a potency of ten?

For example, $4$ is such a number because $4\cdot 25=100=10^2$. I am looking forward to your answers, Robert
0
votes
1answer
36 views

Using Wilson's Theorem to prove Fermat's Little Theorem

My book says that the statement "$\forall a \not \equiv 0 (\mod p)$ and $p$ prime, $a^{p-1} \equiv 1 (\mod p)$" follows from Wilson's Theorem. I'd like to know how. This is what I've looked at so far: ...
12
votes
3answers
751 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is here: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime The challenge is to find the highest ...
1
vote
3answers
24 views

Inequality involving floor function and fractions

I have little to no experience working with floor inequalities so I am kind of stuck on this one. It seems pretty intuitive though. So basically I want to show that ...
1
vote
2answers
41 views

Can't understand source of constant for prime counting function:

Consider the prime counting function $$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$ It is well known due to the sieve eratosthenes that given an integer $n$ and the ...
1
vote
4answers
38 views

Wilson's Theorem textbook proof question

I'm trying to understand this proof from Stein's Elementary Number Theory, and I understand the pairing of inverses but not the other direction. I have two questions: $1).$ When the proof says, $l$ ...
0
votes
2answers
37 views

Work the product $(1+x)(2+x)(3+x)\cdots(p-1+x) \pmod p$ [on hold]

How can I prove that the product $(1+x)(2+x)(3+x)\cdots(p-1+x) \pmod p$ equals $x^{p-1} -1 +p\cdot Q(x)$?
2
votes
1answer
89 views

Is $a^b+b^a$ unique for all integers a and b?

Is $a^b+b^a$ unique for all integers $a$ and $b$? Any proof?
1
vote
3answers
42 views

First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given ...
1
vote
0answers
36 views

On the indivisibility of odd perfect numbers by small numbers

A good day to everyone! This question is an offshoot of the following MSE posts: Odd perfect number divisors Can an odd perfect number be divisible by $101$? My question is as follows: Is ...
11
votes
6answers
2k views

If an inequality is true for all natural numbers, is it necessarily true for all real numbers inbetween?

A lot of the time in lectures, my professors prove (by induction) an inequality (e.g. $(1+x)^n \geq 1+nx$) in the natural numbers (or any subsets thereof), and I've noticed (not rigourously; only by ...
5
votes
2answers
122 views

When is $n!+1$ composite?

I am trying to prove that if $n$ is composite then $n!+1$ is also composite. But I can't. Please help. If it is false then please give the number.
0
votes
0answers
36 views

A different proof of the distributive law for gcd and lcm

I am reading through a textbook (Elements of Abstract Algebra by Clark), and one of the exercises is to show that $$ \operatorname{lcm}(a , \operatorname{gcd}(b,c)) = ...
1
vote
1answer
25 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
-2
votes
2answers
262 views

Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions?

Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions? Suppose $\ a^3 + b^3 = c^3,\ a,b,c \in \mathbb Z^*,\ $then: $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = ...
3
votes
2answers
175 views

Help understanding number theory definition

In my elementary number theory class, we have the following definition which i'm just having trouble understanding what they mean: Definition: A complete system of residues modulo m is a set of ...
0
votes
1answer
94 views

Number theory proof regarding primes and the number of digits of the prime [duplicate]

How would you prove that if given a prime each of whose (decimal) digits is equal to $1$, then the number of its digits is a prime. (It is not known if there exists infinitely many such prime)
0
votes
1answer
145 views

Let $x = 2441921$. Factor $x$ into a product of primes.

Let $x = 2441921$. Factor $x$ into a product of primes. I found that: $1519^2 −x=−134560= −2^5 ·5 · 29^2$ and $1541^2 −x=−67240= −2^3 · 5 · 41^2$. I am trying to figure out what to do from here. ...
0
votes
2answers
67 views

Represent a prime number $p$ congruent to $1$ $\pmod{3}$ by a sum of a square and $3$ times a square

I want to have a proof of the fact that each prime number is the sum of a square and three times a square (Euler). Context I read the answer to my former question about the number of points on an ...
1
vote
4answers
71 views

$p$ prime, $p\mid a^k \Rightarrow p^k\mid a^k$

Suppose $p$ is a prime and $a$ and $k$ are positive integers. Prove that if $pa^k$ then $p^k\mid a^k$. I have already proven that if $a,b,n\in\mathbb{N}$ and if $a^n\mid b^n$, then $a\mid b$. I tried ...
1
vote
1answer
45 views

a square in a finite field of odd order

GF(q) is a finite field of order q, where q is odd. Prove that $a\in GF(q), a\neq0$ has a root in $GF(q)$ iff $a^{(q-1)/2}=1$. I tried to prove it this way: Suppose a has a root in ...
3
votes
3answers
110 views

Does $x^2+x+1 \equiv 0 \pmod {997}$ have solutions? Why or why not?

I'm have difficulty solving this problem in my textbook. Does $x^2+x+1 \equiv 0\pmod{997}$ have solutions? Why or why not? I guess the first step would be $$ \begin{array}{l} (2x+1)^2 \equiv ...
4
votes
0answers
43 views

Computing question: A quadratic which gives primes [on hold]

This is about Project Euler Problem 27. The question is: Considering quadratics of the form $n^2 + an + b$, where $\lvert a \rvert < 1000$ and $\lvert b \rvert < 1000$ Find the product ...
3
votes
2answers
54 views

Prove that every non-prime natural number $ > 1$ can be written in the form of $n+(n+2)+(n+4)+…+(n+2m) = p$

I'm trying to prove that every non-prime natural number greater than $1$ can is equal to a sum of consecutive even or odd numbers. This can be resumed in : « $p,m,n \in ℕ$» , «$p > 1$» , «$n > ...
-1
votes
2answers
50 views

If prime $p = 4k + 1$ and $d\mid k$ , then $\left(\frac{d}{p}\right)=1$ [on hold]

Let $p$ be a prime of the form $p = 4k + 1$ and suppose $d\mid k$. Show that the Legendre symbol $\left(\frac{d}{p}\right) = 1$.
0
votes
2answers
31 views

Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$.

Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$. I have solved the first part but second part need ...
0
votes
2answers
52 views

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$.

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$. My try is let $a$ be a solution of $x^2 \equiv -3 \mod p$. so $a^{p-1} \equiv 1\mod p$. This ...
2
votes
1answer
55 views

Quadratic congruence with composite; $ x^2\equiv\ 31\ ({\rm mod}\ 11^4)$

This is an exercise in Burton I want to know the existence of shorter solution : Solve $$ x^2\equiv 31\ (11^4)$$ Note that we have a algorithm (or program) : If $$ x_k^2\equiv a\ (p^k)$$ then $$ ...
1
vote
1answer
37 views

Primitive roots and quadratic nonresidues modulo a prime of form $2^n+1$

Let $p$ be a prime number. We call a unit $a$ in $\Bbb Z/p\Bbb Z$ a primitive root, if $\text{ord}_p(a)=p-1$. Any unit in $\Bbb Z/p\Bbb Z$ can be written as some power as some power of $a$. if $p$ is ...
1
vote
1answer
20 views

Exercise of Quadratic Reciprocity

This is an exercise in Burton : Prove that $$(5/p) =1\ iff\ p\equiv 1,\ 9,\ 11,\ or\ 19\ (20) $$ Note that $5=4+1$ so that $(5/p)=(p/5)$. In further $$ (p/5)^2=(5/p)(p/5) = (-1)^{1\cdot ...
4
votes
1answer
50 views
+50

Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
0
votes
0answers
29 views

Find a criterion for the primes p such that (5/p) = 1. [duplicate]

Find a criterion for the primes p such that (5/p) = 1. I don't understand this question it is like Determine all primes P such that (5/p)=1 I appreciate any help
0
votes
1answer
34 views

Quadratic Residues in $\mathbb{Z}/3^n \mathbb{Z} $

I was playing around with quadratic residues in $3^n$ modulo systems and am now wondering if there is a neat closed form solution for the set of all quadratic residues in $\mathbb{Z}/3^n \mathbb{Z} $ ...
1
vote
3answers
95 views

Number theory proofs regarding gcd's

How would you prove if $ad-bc = 1$, then $(a+c,b+d)=1$
0
votes
0answers
74 views

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
4
votes
0answers
76 views

Adding Numbers Pattern

A few nights ago I couldn't sleep and so started doing this: I would take a number and add up all of its digits to get a new number and then add up all of those digits and so on until there was only ...
3
votes
2answers
34 views

Middle binomial coefficient mod 4

It is known that the middle binomial coefficient is always even. Show that $\binom{2n}{n}= 2 \mod 4$ if and only if $n$ is a power of 2.
1
vote
0answers
33 views

Which basis orders [for the natural numbers] have been proven?

The set $A$ of nonnegative integers is called an additive basis of order $h$ if every nonnegative integer can be written as the sum of $h$ not necessarily distinct elements of $A$. For example, the ...