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

learn more… | top users | synonyms (1)

6
votes
1answer
167 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
2
votes
2answers
61 views

Prove $10n^8 - 9n^6 - n^2$ is divisible by $45$

Basically, I have to use Euler theorem to prove that $10n^8 -9n^6 -n^2$ is divisible by $45$ So my approach so far is to say $10n^8 - 9n^6 - n^2 = 0 \bmod 45$ Now $45$ can be factored into $5$ and ...
2
votes
2answers
58 views

Integer solutions of $ y^{2} = 5x^{2} + 17 $

Show that there are no integer solutions to the equation $$y^{2} = 5x^{2} + 17$$ using your knowledge of modular arithmetic and congruence classes. My attempt: Take 17 congruence mod 5 and show that ...
0
votes
2answers
24 views

How to find all primitive triples (a,b,c)? (Pythagorean Triples)

how to find all primitive triples when one value of (a,b,c) is given? For example in this case a = 45. What is the procedure to find the primitive triples ? Conditions for primitive triples are: ...
3
votes
2answers
91 views

Find three integers $x$ so that $271x \equiv 272\pmod{2015}$

I know that $\forall{a,n}\in\mathbb{Z}:\Bigl[\gcd(a,n)=1\Bigr]\implies\Bigl[\exists{k}\in\mathbb{Z}:ak\equiv1\pmod{n}\Bigr]$ In other words, for every pair of co-prime integers $a$ and $n$, there is ...
1
vote
1answer
23 views

Legendre Symbol $\left(\frac4p\right)$ is always congruent to $1$?

Let$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}$ $\leg ap$ denote the Legendre symbol. In all cases $a=4$. and $p$ takes values of different odd prime numbers $p$. For $p=5$: $\leg 45$ -> ...
1
vote
1answer
16 views

Prove that $(s-1)!(p-s)!\equiv(-1)^s \pmod p$

A problem asks me to prove: Prove that for $0<s<p$, $$ (s-1)!(p-s)! \equiv (-1)^s \pmod p. $$ Wilson's theorem states that $(p-1)! \equiv -1 \pmod p$. I really have no idea where to ...
1
vote
3answers
31 views

Prove that if $a$ and $a-1$ are relatively prime to $n$ then $1+a+a^2+\cdots+a^{\varphi(n)-1}\equiv 0 \pmod n$

I think I'm off to the right start where I applied Euler's Theorem and got: $$a^{\varphi(n)}-(a-1)^{\varphi(n)}\equiv 0 \pmod n. $$ But I'm not sure how to proceed or if I have the right idea.
3
votes
3answers
42 views

If $p>3$ what are two solutions of $x^2 ≡ 4 \pmod p$?

Theorem used: "Suppose that $p$ is an odd prime. If $p \nmid a$, then $x^2 ≡ a \pmod p$ has exactly two solutions or no solutions." Question: If $p>3$ what are two solutions of $x^2 ≡ 4 \pmod p$? ...
1
vote
2answers
82 views

Find all n such that $\phi(\phi(n)) = 1$

Find all n such that $\phi(\phi(n)) = 1$. I was thinking of firstly writing $\phi(n) = n\prod_{p|n} {1-1/p}$ and then again but I couldn't find a result.
6
votes
2answers
93 views

Prove that $\forall n > 1 \quad2^n - 1 \pmod n \neq 0$

Prove that $\forall n > 1, \quad2^n - 1 \pmod n \neq 0$ I've thought of the induction but I can't figure out how to prove the step. Fermat's theorem (and its variations) aren't particularly useful ...
0
votes
0answers
32 views

Existence of non-coprime between an integer and an arithmetic sequence

Take two relatively prime numbers $m,n \in \mathbb{Z}$ (i.e. $gcd(m,n) = 1$) where $m \neq 1$. Show that: $$\forall a \in \mathbb{Z} \textrm{ s.t. } 0<a<n$$ $$\exists i \in \mathbb{Z^+} ...
2
votes
1answer
50 views

$\phi(n)/n$ is minimal

I am working on a number theory exam and this question seems quite interesting. How do I really approach it? Determine the element $n_k$ of the set {$n \in N: w(n)=k$} for which $\phi(n)/n$ is ...
0
votes
1answer
41 views

Express the following in terms of $\phi$

1. Express $\phi (n^k) $ in terms of n and $\phi(n)$. I know the result is supposed to be $ n^{k-1} \phi(n)$ and I was thinking of approaching it by induction but I am not quite sure. 2. Given $ m ...
1
vote
2answers
27 views

Number of reduced fractions in terms of Euler's totient function

Find the number of reduced fractions $\frac{a}{b}$ with $1 \le a < b \le n$ in terms of Euler's totient function. I was thinking that is should be of the form $\phi(1) + \phi(2) + \ldots + ...
3
votes
2answers
54 views

Is fibonacci sequence a member of more broad family of sequences?

Yesterday, I was pondering on the Fibonacci sequence and I started to discover some features of it that were previously unknown to me. Such as, 1, 1, 2, 3, 5, 8, 13, 21, 34 .... 1 ) The nth element ...
3
votes
2answers
35 views

Find $n$ such that $(m-1)(m+3)(m-4)(m-8)+n$ is a perfect square for all $m$

Find $n$ such that $(m-1)(m+3)(m-4)(m-8)+n$ is a perfect square for all $m$ I am thinking of starting like this $(m-1)(m+3)(m-4)(m-8)+n = k^2 \implies (m-1)(m+3)(m-4)(m-8) = k^2-n$ Honestly ...
-1
votes
0answers
602 views

$ (x+y) \geq (p_n +2) $?

I recently worked on a previous idea of mine (a prime number inequality, which I had posted in this community but didn't know Latex then and couldn't discuss it's proof). I was wondering how powerful ...
0
votes
2answers
42 views

Finding order of an integer with (mod 9)?

I am trying to solve a problem to find the order of some integers with (mod 9). I understand the concept I also have the solution to the problem. My calculations are also correct except for a few ...
0
votes
1answer
37 views

Suppose that $p$ is prime. If $a$ and $b$ are integers for which $a^p \equiv b^p \pmod{p}$, then how do I prove that $a \equiv b \pmod{p}$.

I saw the explanation of it here using Fermat's Little Theorem but I do not get how I can go from $a^p \equiv a \equiv b^p \equiv b \pmod{p}$ because of transitivity (I guess I want to ask what is ...
2
votes
8answers
1k views

When is a number even?

Why does something like $a^2 = 2b^2$, show that $a^2$ and thus $a$ are even numbers? My feeling is that it's because one can divide $a^2$ by two and hence it must be even. Can anybody give me a ...
1
vote
2answers
27 views

Let $k = (a+b,a^2+b^2-ab)$. If $(a,b)=1$ then $k = 1$ or $k=3$.

Yes, I know that this questions has two answers, but I can't see why $k$ can't be 27, or any other $3^n$ with $n \neq 2$.
0
votes
2answers
68 views

Find j,k such that $2^j + 3 = 7^k$

Find all $j,k$ such that $2^j + 3 = 7^k$. I think that the only solution is $j=2$. Because of the exponential growth of $2$ and $7$. But I am not that sure.
4
votes
2answers
69 views

Show the following if $p$ is prime

If $p$ is prime and $ a \ge 2$, prove that $$ d = (a - 1, \frac{a^p - 1}{a - 1}) = \begin{cases} p & \text{if } p \mid (a - 1)\\ 1 & \text{if } p \nmid (a - 1) \, . \end{cases} $$ I was ...
-3
votes
1answer
67 views

Elementary Number Theory

Let '$a$' be an integer and '$n$' a positive integer. Prove or provide a counter example to each of the following three statements. If $a\equiv \pm 1 \pmod{p}$ for all primes '$p$' dividing $n$, ...
0
votes
3answers
40 views

Find all the positive natural solutions of $x^2+y^2=3z^2$. [duplicate]

Find all the positive natural solutions of $x^2+y^2=3z^2$. I guess it has something to do with Pythagorean triples, but I don't know how to relate it properly. Suggestions, hints, or any sort of ...
0
votes
0answers
25 views

$j$-volume of $j$ dimensional parallelepiped inside $\mathbb{R}^n$

Let $v_1, ..., v_j \in \mathbb{R}^n$ be linearly independent. Let $V = \mathbb{R}v_1 + ... + \mathbb{R} v_j$ be a subspace of $\mathbb{R}^n$ and $\Gamma = \mathbb{Z}v_1 + ... + \mathbb{Z} v_j$ a ...
2
votes
2answers
40 views

Prove that if $\gcd(m,n)=1$ then every divisor $d|mn$ has a unique form $d=ab$ such that $a|n$ and $b|m$.

I can see why this is true. I have a problem with formality or with explaining certain things properly. An attempt: suppose there are two forms $d=a_na_m=b_nb_m$ such that $a_n,b_n|n,a_m,b_m|m$ but ...
2
votes
1answer
55 views

Number Theory : Show that $\sigma(n)$ $=$ $2n$ for $n$ $=$ $(2^{m-1})$ $(2^{m} -1)$

I was working through some basic Number Theory Problems when I came across : Given an integer $m$ $≥ 2$ such that $(2^{m} -1)$ is a prime, and $n$ $=$ $(2^{m-1})$$(2^{m} -1)$, then show that ...
2
votes
3answers
79 views

Number Theory : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$

I was working my way through some basic Number Theory Problems , when I came across : Find the values of $x$ for which $\phi(x)=\frac{x}{3}$ , where $\phi(x)$ is the euler phi function I am ...
5
votes
3answers
83 views

Why can $5^{2n+3} + 3^{n+3} \cdot 2^{n} \quad \forall n \in \mathbb{N}$ never be a prime number?

It seems to be true for the first thousand $n$ but I really can't think of a way to prove this statement. Any kind of help will be appreciated!
2
votes
1answer
82 views

A generalization of Goldbach's conjecture?

In a previous question I asked about a counterexample for an observation I did about the Goldbach's comet: it seems that there is always common prime shared between the Goldbach's prime pairs of the ...
4
votes
6answers
110 views

Proof that $a+\frac{1}{a}\in\mathbb{Z}$ iff $a=\pm1$

I showed someone how to prove by induction that if $a+\frac{1}{a}\in\mathbb{Z}$ then also $a^n+\frac{1}{a^n}\in\mathbb{Z}$. He noted that there was no need for induction since obviously ...
6
votes
1answer
89 views

Proving $\,2\sqrt 2 + 1\,$ is irrational by contradiction

I am working on some review questions for my Discrete Structures final and I needed some assistance for the problem "Prove by contradiction that $\,2\sqrt 2 +1$ is irrational". Now I know how prove ...
5
votes
1answer
59 views

A question about Euler's totient function

Prove that for every natural number $m$, there exists a natural number $n$ such that $$\phi(n)=\phi(n+m)$$ For odd numbers $m$, we can choose $n=m$ and use the identity $\phi(2m)=\phi(m)$.
6
votes
1answer
102 views

The totient of Fibonacci numbers is divisible by $4$

Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient ...
2
votes
8answers
331 views

A pedagogical proof that 9's can be ignored when calculating digital roots

I was asked by an elementary school teacher for a proof that you can ignore all 9's when calculating the digital root of a number. For instance, when calculating the digital root of 7593329, you ...
3
votes
2answers
52 views

Solving the diophantine equation $p^2+n-3=6^n+n^6$

What are the pairs ($p,n$) of non-negative integers where $p$ is a prime number, such that $$p^2+n-3=6^n+n^6$$ How can I solve this diophantine equation?
4
votes
5answers
199 views

What is $2^{7!}\bmod{2987}$

Find the remainder when $2^{7!}$ is divided by $2987$. I tried to factorise $2987$ to make it simple but it was in vain.
2
votes
2answers
36 views

The greatest common divisor

Problem : Confirm the following properties of the greatest common divisor: If $\gcd(a,b) = 1$, and $c \mid (a+b)$, then $\gcd(a,c) = \gcd(b,c) = 1$. Is this right? This is my answer: $\gcd(a,b) ...
1
vote
1answer
35 views

combinatorial of $\binom{10^9} {r}$ while $1 \leq r \leq10^9 \pmod {10^6+3}$

How to calculate $ \binom{n}{r} \mod m$ when $1\leq n,\: r\leq 10^9$ and $m=10^6+3$. I have tried by making Sieve of factorial and multiplicative inverse $10^6+3 \mod m$. is there any solution in ...
0
votes
0answers
28 views

Proofs of Norms in Quadratic Field

Question Suppose $α$ and $β$ are elements of $Q[√d]$. Show that $N(αβ) = N(α)N(β)$ and that $N(α/β)=N(α)/N(β)$. In the case where $α ∈ Q$, show that $N(α) = α^2$. My Work For the first two can ...
0
votes
1answer
37 views

Find norm in $\mathbb Q[\sqrt{5}]$

I did not get any response, so I am posting my question again. Question: Find a defining equation for the golden ratio: $\frac{1{+}\sqrt{5}}{2}$. Also find its norm in $\mathbb Q[\sqrt{5}]$. My ...
1
vote
1answer
44 views

Using number theory to solve $x^3 \equiv 1 \pmod {19}$

I'm trying to find all solutions to $x^3 \equiv 1 \pmod{19}$. I understand that there are various ways of solving it, such as looking at the Cayley table for $U(\mathbb{Z}_{19})$, the multiplicative ...
6
votes
3answers
470 views

What is the difference between natural numbers and positive integers?

I was reading sets and came to some reserved letters for a few sets. Two of them really confused me. They were - N : For the set of natural numbers. Z+ : For the set if all positive integers. In ...
2
votes
3answers
52 views

Proving that ${1^n,2^n,3^n,…,(p−1)^n}$ is a reduced residue system modulo $p$ if $(n, p-1)=1$

My problem is identical to that of this person's. However, I'm not quite sure I understand the hint given in the best answer. Is there perhaps another method of solving this problem? I'm not very good ...
4
votes
1answer
58 views

How many values of $k$ satisfy $\left (\frac{k}{p}\right )=\left (\frac{k+1}{p}\right)=1$ where p is a odd prime?

The values of $k$ must be between $1$ and $p-1$ this means : $$k\in\left\{1,2,\cdots,p-1\right\}$$ The question: Given an odd prime $p$ What is the number of elements ...
0
votes
1answer
23 views

Equation considering $\mathbb Q[\sqrt{-1}]$ and $\mathbb Q[\sqrt{d}]$

So first consider $\mathbb Q[\sqrt{-1}]$. Now, can someone explain to me and show me an equation relating $N(α)$ to $|α|$. For info, $|α|$ is the natural absolute value defined for complex numbers. ...
6
votes
2answers
208 views
+100

diophantine equation $x^3+x^2-16=2^y$

Solve in integers: $x^3+x^2-16=2^y$. my attempt: of course $y\ge 0$, then $2^y\ge 1$, so $x\ge 1$. for $y=0,1,2,3$ there is no good $x$. so $y\ge 4$ and we have equation $x^2(x+1)=16(2^z+1)$, ...
27
votes
2answers
514 views

Prove that $\frac{a^n-1}{b^n-1}$ and $\frac{a^{n+1}-1}{b^{n+1}-1}$ can't both be prime.

Prove that $$\frac{a^n-1}{b^n-1} \ \text{and} \ \frac{a^{n+1}-1}{b^{n+1}-1}$$ cannot both be prime ($a>b>1,n\ge 2$). Clearly $(a^n-1,a^{n+1}-1)=a-1$ and $(b^n-1,b^{n+1}-1)=b-1$. ...