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

learn more… | top users | synonyms (1)

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
32 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
41 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 ...
2
votes
1answer
27 views

Is there a standard term for this generalization of the Euler totient function?

Let $\phi_k(n)$ be the number of integers $m$ in $1\le m\le n$ for which $\gcd(m,n) = k$. Then $\phi_1(n) =\varphi(n)$, the standard totient function. This function arises in the analysis of the ...
5
votes
1answer
68 views

Theoretical way to prove no positive integer $n$ exists such that $n+3$ and $n^2+3n+3$ are both perfect cubes.

I have to prove that for any positive integer $n$ at least one of $n+3$ and $n^2+3n+3$ is not a perfect cube. Is there a methodical way to solve this problem? I managed to solve it by contradiction, ...
4
votes
3answers
68 views

Given positive integers a and b such that $a\mid b^2, \:b^2\mid a^3, \:a^3\mid b^4,\: b^4\mid a^5$…, prove $a=b.$ [duplicate]

Given positive integers a and b such that $a\mid b^2, \:b^2\mid a^3, \:a^3\mid b^4,\: b^4\mid a^5$..., prove $a=b.$ I was able to show that a and b have the same primes in their factorizations, ...
3
votes
2answers
46 views

Divisibility of numbers

Find all positive integers $x,y$ such that $2x+7y$ divides $7x+2y$. I somehow managed to show that $x$ is greater than $y$. But couldn't proceed further.
0
votes
5answers
70 views

Prove that $n^3=n \text{ mod }6$ for every integer $n$. [duplicate]

Prove that for every integer $n$ , $n^3=n \text{ mod }6$ I was having no clue how to do this, then I thought of case-by-case analysis and obviously it worked. The problem is that there were six case ...
-3
votes
2answers
64 views

Non-negative integer solutions to $x+2y+3z=104$ and $3y+4z=60$

$x+2y+3z=104$ $3y+4z= 60$ I am trying to find the non-negative integer solutions, of which I know there are six, but I do not know how to get them. Are there any easy methods of doing this?
2
votes
2answers
50 views

statements including Mobius Inversion Formula

Find a simple formula for $f(n) = \sum \limits_{x|n} \mu(x) \tau(x)$ $f(n) = \sum \limits_{x|n} \sigma(x) \mu(n/x)$ which I believe is equal to n. $f(n) = \sum \limits_{x|n} \mu(x) \mu(n/x)$. ...
1
vote
2answers
38 views

Relevance of prime being divisble by $4k+1$ in proof that 'There are infinitely many primes of the shape $4k+3$'

Show that there are infinitely many primes of the shape $4k+3$ Proof: $1)$ Suppose that there are only finitely many such primes, say $p_1,...p_n$. $2)$ Consider the integer $Q=4p_1...p_n-1$ $3)$ ...
0
votes
1answer
26 views

Simple question in number-theory

$a, b, c$, and $d$ are integers. From exactly one of the equations $A, B, C, D, E$, one can deduce that $14$ divides $a \cdot b$. Which one? A) $7a+8b=14c+28d$ B) $14a+28b=7c+8d$ C) ...
0
votes
2answers
27 views

Converse of Bézout's identity

Given that we know gcd$(a,b)=sa+tb$ where $s,t \in \mathbb Z$, I wonder is the converse true? I.e., can we say that the value of $ax+by$ is the gcd of any $2$ of $a,x,b,y$?
0
votes
2answers
31 views

Solving an inequality involving a floor

Increasing the integer $k$, I can make the floor of $L/k$ smaller than $r$: $$\left\lfloor \frac{L}{k} \right\rfloor \lt r$$ where $L, k, r$ are positive integers, $k\leq \lfloor \frac{L}{2} ...
1
vote
0answers
41 views

Multiple of power of 5 with only the digits 2,5,6

after helping a friend solve a homework, I asked myself the following question: $H\subseteq\{1,2,\ldots,9\}$, $T(H)=\{n\in\mathbb{N}:$ all the digits in the decimal representation in $n$ belong to ...
3
votes
1answer
31 views

Proving the equivalence of a finite set

Let A be a finite set. Prove that if A≈􏰔n and A≈􏰔m, then n=m. The answer in the book uses a max function, so I was just wondering if there was a simpler way. If not, it would be appreciated if ...
1
vote
1answer
21 views

Given $2^n$, what is the largest power of $2$ that will divide any random concatenation of base $10$ digits of powers of $2$ ending with $2^n$?

My first thought was that it would be $2^n$ itself, for example, if you concatenate $4$ and $2$ to get $42$, that's divisible by $2$ but not by $4$. But whit $2^9 = 512$, you can concatenate $16$ and ...
3
votes
1answer
54 views

Prove by induction $n= qb+r$ for $ n\ge 0$

Let $b$ be a fixed positive integer . Prove by induction for all $ n\ge 0$ there exists $q$ and $r$ non-negative integers ( positive integers + 0) that $n= qb+r$ for $0 \le r < b $ my try its not ...
2
votes
2answers
43 views

Find the number $abc$

The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base 10, where digit $a$ is not zero. Find the three-digit number $abc$. $$N \equiv abcd ...
2
votes
1answer
47 views

I suppose this is a familiar number-theoretic operation, but what is it?

Define a function $/\!/ : \mathbb{Z}_{\geq 1} \times \mathbb{Z}_{\geq 1} \rightarrow \mathbb{Z}_{\geq 1}$ as follows: given integers $j,k \geq 1$, we have: $$k/\!/j = \min\{n\in\mathbb{Z}_{\geq 1} : ...
0
votes
2answers
36 views

converting numbers to degree

I have 0 to 1 that represent 0 to 360 degrees I know that 0.5 would represent 180 degrees but what formula would I use to get the other vales for 0 to 1. Thanks
8
votes
3answers
102 views

Minimal $ab$ for Rational Number $a/b$ in an Interval

Given rational numbers $L$ and $U$, $0<L<U<1$, find rational number $M=a/b$ such that $L \le M<U$ and $(a\times b)$ is as small as possible---$a$ and $b$ are integers. For example, If ...
-1
votes
0answers
25 views

Application of Cauchy-Schwartz to an exponential sum involving von Mangoldt function

Let $f(x_1, ..., x_n)$ be a polynomial in $\mathbb{Z}[x_1, x_2, ..., x_n]$. Let $\Lambda$ denote the Von Mangoldt function. Suppose I have an exponential sum of the form $$ S(\alpha) = \sum_{1 \leq ...
6
votes
1answer
126 views

Show that the number of reduced residues $a \mod m$ such that $a^{m-1} \equiv 1 \mod m$ is exactly $\prod_{p \mid m} \gcd(p-1,m-1).$

Show that the number of reduced residues $a \mod m$ such that $a^{m-1} \equiv 1 \mod m$ is exactly $$\displaystyle \prod_{p \mid m} \gcd(p-1,m-1).$$ Suppose $f(x) = x^{m−1}−1$ and let $m = ...
2
votes
1answer
61 views

What is $13^{498}$ (mod $997$)? [duplicate]

I have to determine $$13^{498} \pmod{997}$$ I know that it can only be $1$ or $-1$. But I don't quite know which. How can I decide?
1
vote
1answer
36 views

If $\gcd(a,b)=d$, then $\gcd(a/d, b/d)=1$

So, I think that I understand the proof. The idea is that we want to establish the inequality that says that $c\leq 1$ and with the idea that the $\gcd$ of two numbers is always greater or equal ...
4
votes
2answers
41 views

prove that $n^2 \bmod 4 = 0$ or $1$ for all integers

(Use the fact that every integer is either even or odd to prove that $n^2 \bmod 4 = 0$ or $1$ for all integers) Let $n \in \mathbb{Z}$, then $n$ is either even or odd. Case 1: ($n$ is odd): By ...
3
votes
1answer
40 views

$n^{q}\equiv1~(\text{mod $p$})$ is possible solve this? [closed]

I have the following situation: Let $p, q$ be a prime numbers were $p>q$ and $n\in\{0,1, \ldots, p-1\}$. In this conditions is possible solve (in function of $n$) this equation, ...
2
votes
1answer
41 views

Use Gauss' Lemma to find Legendre symbol $\left(\frac{-1}{n}\right)$ for $n \equiv 1, 3, 5, 7 \pmod 8$.

I know that if $ n \equiv 1 \pmod 4$, then $\left(\frac{-1}{n}\right)=1$, but in this case we are dealing with mod $8$. If $n \equiv 1 \pmod 8$, then $n=1+8k$. So, $(8k+1-1)/2=4k$. So, we have: ...
1
vote
1answer
79 views

Pointy triangles exists

In Yahoo Answers, here, Rita the dog defined a pointy triangle, (more or less) as having three properties. The lengths of two sides are rational and greater than 1. The length of the third side is ...
4
votes
3answers
69 views

prove that if $5| n^2$ then $5|n$ by contraposition

let $ n \in \mathbb{R}$ suppose $5\nmid n$ then by definition of divides n = dk+r where $d \in \mathbb{Z}^{+}$ $k \in \mathbb{Z}$ and $d \neq 5$ and $0 < r \le 5$ Can someone help me finish ...
0
votes
1answer
31 views

Finding the integer parts of irrationals

When working with continued fraction expansions, I sometimes have to calculate the integer part of irrationals quickly without a calculator, what would be an effective way to do this? For example, ...
1
vote
1answer
52 views

Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ ...
2
votes
2answers
199 views

Parameterization of Natural Numbers

Suppose we have 4 positive integers $a<b<c<d$ such that $a+d=b+c=n$, i.e. $a,d$ and $b,c$ have the same average. Does there exist $p,q,r,s \in \mathbb Z$ such that \begin{equation*} ...
1
vote
2answers
66 views

What does $(n|p)=1$ mean?

My number theory book mentions the following condition: $(n|p)=1$, where $p$ is prime. What does $(n|p)=1$ mean? I used to think $n|p$ implies that $n$ divides $p$.
-1
votes
0answers
9 views

Generate a number set such that the sum of the set details the contents

I have a set of numbers. I want to save space storing my numbers, so I am only interested in the sum of the set (which I assume will require fewer bits to represent than the set). How can I generate ...
3
votes
2answers
48 views

How to prove that if $m$ is squarefree, then $d^2 \lvert mb^2 \implies d \lvert b$

This statement was given in my number theory textbook when analyzing quadratic fields, and I am not seeing how to prove it. $m$ is a squarefree (not divisible by the square of any number) integer and ...