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

learn more… | top users | synonyms (1)

0
votes
1answer
24 views

Show that 2 is not primitive modulo $p=2^{2^n}+1$ for $n\ge 2$, p prime.

Show that 2 is not primitive modulo $p=2^{2^n}+1$ for $n\ge 2$, p prime. My problem is that I can't prove by contradiction, because logically I can't say "suppose there isn't $m<\phi(p)$ such that ...
0
votes
2answers
35 views

How to replace these two equations by one equation.

Let $x$ be natural number such that $\begin{cases} x=5k+3\\ x=3l+1 \end{cases}$ $k,l\in \Bbb N$ WolframAlpha says that $x=15n+13, n\in \Bbb N$. That's right because: $15n+13=5(3n+2)+3=5k+3$ ...
1
vote
1answer
22 views

Check membership in set of bisquares

A bisquare is a number which can be expressed as $p^2 + q^2$ where $p,q\in\mathbb{W} $. Given a number, how can you quickly tell if it is a bisquare or not? Is it even possible to do so without using ...
1
vote
0answers
29 views

Show 3 is a primitive root modulo $7^n$ for $n\in \Bbb{N}$. [duplicate]

I tried induction but got stuck. For $n=1$ it is true. Suppose it holds for $n$, i.e, the order of 3 is $\phi(7^n)$. Now I should prove it for $\phi(7^{n+1})=6\cdot 7^n$. $7^n\mid3^{6\cdot 7^n}-1$. ...
1
vote
1answer
42 views

Show that there are infinitely many primes $p$ of the form $p=a^2+b^2+c^2+1$

I know that any prime can be written as the sum of four squares. But I don't know how to know one of these squares is $0$.
1
vote
1answer
17 views

How are equation of that form $a^x\equiv b \mod n$ often named?

How are equation of that form $a^x\equiv b \mod n$ usually named? I am trying to solve $7^x\equiv 6 \mod 17$ but I am having troubles doing so for I don't know enough properties of this kind of ...
0
votes
0answers
29 views

Can you help me write this $n^n$ related sequence so that the sum over divisors notation is used?

I need help writing the following sequence: $$a(n)=0,\frac{\log (2)}{2},\frac{1}{3} \log \left(\frac{9}{2}\right),\frac{1}{4} \log \left(\frac{32}{3}\right),\frac{1}{5} \log ...
2
votes
2answers
29 views

Check for an equivalence relation on the integers

Given the set of integer $\mathbb Z$, define $\sim$ as $x\sim y$ precisely when $2$ divides $x-y$. I'm having a hard time showing that the three properties of an equivalence relation hold. Any help ...
3
votes
2answers
54 views

Prove that the sums of the reciprocals of the primes diverge using $\frac{1}{p_{j+1}}+\frac{1}{p_{j+2}}+\frac{1}{p_{j+3}}+\cdots>\frac{1}{2}$

Prove that the sum of the reciprocals of the primes diverge, i.e show that: $$\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}+... Diverges$$ The hint I got: To show that the sum of the reciprocals of the ...
2
votes
1answer
26 views

Proving that $n|x^ {φ(n)/2} − 1$ for every $x$ coprime to $n$.

Let $n \in \Bbb{N}$ for which there exist two coprime numbers bigger than 2 dividing n. Show that for every x coprime to n we have $n|x^ {\phi(n)/2} − 1$. Conclude that there is no primitive root ...
1
vote
1answer
39 views

A question on Primes in Arithmetic Progression

We know that an arithmetic progression has to have a composite number since there are arbitrarily large gaps between primes. But I was wondering whether the following construction is possible: Can ...
0
votes
0answers
13 views

Are integral combination and linear combination the one and the same in the field of number theory?

My question is a trivial question as to the exactness of the meaning of integral and linear in the study of the number theory. Do they hold the same meaning?
1
vote
0answers
26 views

Estimating the number of elements with a given least prime factor in a sequence of consecutive integers

Let $a,n$ be any positive integers. Let $\varphi(x)$ be the Euler totient function. It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will ...
2
votes
1answer
54 views

For what values of $n$ , does $7 \mid 5^n+1$

$7 \mid 5^n+1$ implies $5^n+1=7a$ for some integer $a$ i.e $5^n=7a-1$ Now , $5^n$ is an integer which always ends with $5$ [for any integer $n$]. Thus , $7a-1$ must also end with $5$.But , this is ...
1
vote
2answers
46 views

2 questions in Number Theory about primitive roots/quadratic residue

I tried to solve this 2 questions but without a success: Is $13$ a sixth power modulo $289$? Find all the solutions of $x^{8}\equiv 3\mod 13$ In question 1, I tried to see if $13$ is a quadratic ...
1
vote
0answers
62 views

Problem with multivaluedness of $(-1)^{\frac 14}$

Assume that $p\equiv3\mod4$ is an odd prime and $k$ an odd number. Then $$m=(-1)^{\frac{p^k-p^{k-1}+2}{4}}$$ seems to be always the value $1$ (?). This would be interesting how one can prove this - I ...
2
votes
1answer
37 views

Prove that $x$ is either an integer or irrational

How do I prove that if $x$ is a root of the polynomial: $$x^m+c_1(x^{m-1})+c_2(x^{m-2})+...+c_m=0$$ then $x$ is either an integer or irrational. $c_1,c_2,...,c_m$ are all integers What I thought: ...
0
votes
0answers
29 views

Find all solutions to the Diophantine equation or show that none exist [duplicate]

The equation is $17x^4 + 5y^4 = 35z^4$ I reduced $\pmod 5$ but that just told me $x$ has to be a multiple of $5$. Not sure where to go from here. Any help would be appreciated. I've only taken an ...
0
votes
1answer
45 views

Show that if $n$ is fixed, then $\phi(x) = n$ has only a finite number of solutions [closed]

Where $\phi(x)$ is the number of integers, $1\leq i \leq x$, such that $GCD(i, x) = 1$.
1
vote
3answers
47 views

Divisibility number theory problem

How many $k,m$ exist such that $ \frac {k^2+m^2}{2(k-m)}$ is also an integer. $k,m \in \mathbb {Z} ^ + $ My guess that there is finitely many solutions but I can't seem to be able to prove so.
1
vote
1answer
26 views

Number theoretic function related to totient

I'm doing an excercise in Alan Baker's book A Concise Introduction to the Theory of Numbers, and I'm confused about the method spelled out for one question. I'll quote it here: Let $a$ run through ...
10
votes
2answers
428 views

Application of Taylor's Theorem in Number Theory

I'm working through Alan Baker's book A Concise Introduction to the Theory of Numbers, and there's an assertion in there that confuses me. Here's the quote: It is easily seen that no polynomial ...
0
votes
2answers
40 views

An infinite square arithmetic progression? [duplicate]

How to prove that there does not exist and infinite arithmetic sequence that all of it's terms are distinct squares of integers?
5
votes
5answers
81 views

What is the biggest $n$ in $4^n$ that divides $7^{2048} - 1$?

A few days ago I stumbled on the following question, it was used in the Museum of mathematics masters tournament: What is the biggest integer $n$ in $4^n$, that divides $7^{2048} - 1$? a) 1 b) 3 ...
2
votes
2answers
32 views

Proofs for Multiplicative Functions in Number Theory

Part 1: A theorem in my book proves that if $f(n)$ is a multiplicative function, and $g(n)=\sum_{d|n}f(d)$, then $g(n)$ is also multiplicative. How do I prove the converse of this. The converse being ...
1
vote
4answers
43 views

Write $xy$ as the sum of the squares of two rational integers

Show that if $x$ and $y$ may both be written as the sum of the squares of two rational integers, then their product $xy$ may also be written as the sum of the squares of two rational integers.
1
vote
2answers
49 views

Show that $p$ isn't a prime in $Q[\sqrt{-1}]$

I am working with Gaussian Integers. Part 1: Suppose $p$ is a rational prime congruent to $1$ mod $4$. How do I show that $p$ isn't a prime in $Q[\sqrt{-1}]$ Part 2: Using part 1 I need to show ...
1
vote
1answer
16 views

$N(α) | N(β)$, yet $α$ does not divide $β$

What would be an example of two quadratic integers in the same quadratic field for which $N(α) | N(β)$, yet $α$ does not divide $β$.
3
votes
1answer
96 views

Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)

While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
1
vote
2answers
33 views

A question on perfect square

Prove that if $ab$ is a perfect square and $\gcd(a,b)=1$, then both $a$ and $b$ must be perfect squares. Their Answer: Consider the prime factorization $ab=p_1^{e_1}\cdots p_k^{e_k}$. If $ab$ ...
1
vote
1answer
24 views

Prove that $f$ is a multiplicative function and calculate the Summatory Function

Define $f(n)$ as $1$ if $n$ is odd, and $3$ if $n$ is even. So i have $f(odd) = 1$ and $f(even) = 3$ If a function $f$ is multiplicative then if $gcd(m,n) = 1$ then $f(m * n) = f(m) * f(n)$ This ...
3
votes
1answer
57 views

Find all pairs of primes $p,q$ such that $pq \mid 2^p +2^q$

Find all pairs of primes $p,q$ such that $pq \mid 2^p +2^q$. My attempt : When either one of them is $2$ then easy case checking gives me set of solutions. But what happens when neither of them is ...
0
votes
2answers
42 views

Not the sum of the squares of two rational numbers

It is easy to see that $7$ isn't the sum of the squares of two integers. However, I want to show why it isn't. Can someone show me a proof as to why $7$ is not the sum of the squares of two rational ...
0
votes
2answers
31 views

Show that $3\mid xy$ in $x^2 + y^2 = z^2$

Part 1: If $x$, $y$, and $z$ are positive integers for which $gcd(x, y, z) = 1$ and $x^2 + y^2 = z^2$, show that $3\mid xy$ Part 2: Now again if $x$, $y$, and $z$ are positive integers for which ...
1
vote
1answer
10 views

Prove $3$ is a primitive root modulo $p$ given $\;p\equiv 2 \;\text{mod}\; 3\;$, $\;p-1=4q\;$, for $q$ prime.

Let $p$ be a prime number which satisfies the following two conditions: (i) $p\equiv 2 \;\text{mod}\; 3$ (ii) $p-1=4q$ where $q$ is also a prime number. Show: (a) that $3^4\not\equiv 1\; ...
4
votes
3answers
85 views

Finite or Infinite n in $φ(n)$ [duplicate]

Are there finitely or infinitely many integers n for which $φ(n) = 1000$? I think that there are finite, but I don't know how to prove it.
2
votes
2answers
41 views

If $a,b,c, \frac{a}{b}+\frac{b}{c}+\frac{c}{a}, \frac{b}{a}+\frac{c}{b}+\frac{a}{c} \in \mathbb{Z}$ prove that $\displaystyle |a|=|b|=|c|$.

If $\displaystyle a,b,c \in \mathbb{Z}$ and $\displaystyle \frac{a}{b}+\frac{b}{c}+\frac{c}{a}$ and $\displaystyle \frac{b}{a}+\frac{c}{b}+\frac{a}{c}$ are also integers then prove that $\displaystyle ...
0
votes
1answer
31 views

Factor $x^4-4$ into irreducible factors over $\mathbb{Q}$, over $\mathbb{R}$, and over $\mathbb{C}$

Factor $x^4-4$ into irreducible factors over $\mathbb{Q}$, over $\mathbb{R}$, and over $\mathbb{C}$ So for $\mathbb{Q}$ and $\mathbb{R}$, I can get some factors in the $\mathbb{C}$. but what I ...
0
votes
3answers
23 views

Show that if $p$ is a prime number and $a$ is an integer, and if $p \mid a^2$ , then $p \mid a$.

I am suppose to make use of the following lemma If $a$, $b$ and $c$ are positive integers such that $(a, \, b) = 1$ and $a \mid bc$, then $a \mid c$ to prove that if $p$ is a prime number and ...
0
votes
1answer
40 views

Parametric characterization for $x^2 + y^2 = 2z^2$

What would be a parametric characterization of all relatively prime solutions in positive integers to $x^2 + y^2 = 2z^2$? The hint I got was: Show there are integers $a$ and $b$ for which $x = a+b$ ...
1
vote
2answers
39 views

If $n^2=ab$ and $\gcd(a,b)=1$, show that $a,b$ are not necessarily squares.

I'm reading Stillwell's: Elements of Number Theory If $a$ and $b$ are relatively prime integers whose product is a square, show by means of an example that $a$ and $b$ are not necessarily squares. ...
0
votes
1answer
31 views

Prove by induction that every integer is either a prime or product of primes

Let $n$ and $d$ be integers such that $d$ is a divisor of $n$ if $n=ad$ for some integer $a$. A prime number is a integer $n>1$ that is divisible by 1 and itself. Prove by induction that every ...
5
votes
3answers
52 views

$a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 ...
3
votes
1answer
45 views

Finding the numbers of primes $<n$ by counting sums of two squares

I start by considering Fermats theorem that $4n+1$ primes are the sum of two primes. I then consider all such sums of positive integers $x$ and $y$ such that $x^2+y^2<n$ These can be found in in a ...
1
vote
2answers
29 views

quadratic reciprocity

I know $x^2\equiv-7\pmod7$ has solutions. How can I check if $x^2\equiv-7\pmod{49}$ has solutions? I know $-7\equiv42\pmod{49}$ but $49$ isn't a prime so I can't use Euler's criterion. How shall I do ...
-1
votes
1answer
42 views

How do we prove that $(k!)^2$ is factor of $(2k + 2)!$ for any positive integer $k$? [closed]

Prove that $(k!)^2$ is a factor of $(2k+2)!$ for any positive integer $k$.
1
vote
1answer
29 views

An elementary proof in Number Theory

How can i prove this statement; if $p$ is a prime then; $2^p - 1$ is divisible by no prime other than those of the form $2kp+ 1$
1
vote
0answers
16 views

The lower bound of the number of cubic residue mod n. [duplicate]

For arbitrary positive integer $n$ , Denote $a\sim_n b \iff a^3\equiv b^3 \mod n$, and $P(n):=\mathrm{Card}\{\mathbb{Z}/\sim_n\}$, How to calculate the value ...
0
votes
0answers
21 views

How to simplify my formula related to Lissajous figure?

How could I simplify the following formula? ...
2
votes
0answers
29 views

If $q$ is a prime, $gcd(x(x+2),q\#)=1$ and $q < x < q^2$, doesn't it follow that $x,x+2$ are twin primes?

I recently asked a question that was not well received. That's ok. I don't disagree with the ratings if my question is unclear. I want to verify the foundation of my reasoning. Doesn't it follow ...