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

learn more… | top users | synonyms (1)

1
vote
0answers
42 views

Characteristic polynomial and Generating Function for recurrence relation of an integer sequence

Given an integer sequence, such that for $n > 2$, $a_n$ = greatest number of the form gpf $(a_{n-1})k$ + spf $(a_{n-2}) \le n^{2}$. Where gpf denotes the Greatest Prime Factor and spf the Smallest ...
2
votes
1answer
113 views

“Practical” Sieve of Eratosthenes from “Primes Numbers - A Computational Perspective”

Consider the following pseudocode for the Sieve of Eratosthenes, giving us the primes up to $N$: 1) List the numbers $2$ to $N$. 2) Let $p=2$. 2) Cross out $p^2$, then cross out $(p+1)p, (p+2)p, (...
9
votes
0answers
87 views

Integer polynomials with roots in every $\mathbb{Z}_p$ but no rational roots.

I want to find polynomials in $\mathbb{Z}[x]$ with degree as small as possible such that these polynomials have no rational roots but have a root in the $p$-adic integers $\mathbb{Z}_p$ for every ...
1
vote
0answers
41 views

List of positive integers from $1$ to $N$ that is NOT divisible by a list of prime numbers.

Give a list from $1$ to $N$ where $N$ is a positive non-zero integer and a list of prime numbers $p$, $q$, $r$, etc. What are the number of cases left from the $N$ list that are not a divisible by any ...
7
votes
2answers
146 views

Is there a mathematical statement that is linking integer limits to real limits?

I saw a question asking for the limit $$\lim_{n \to \infty}\frac{\tan(n)}{n}.$$ At first I thought that the limit assumed $n$ to be a real number. So I gave the advice to use $\pi/2+2\pi k$ and $2\...
0
votes
2answers
86 views

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(6^n-4,2^n-3)=1$ [duplicate]

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(6^n-4,2^n-3)=1$ where $n$ is a natural number. I was thinking of using something with the Euclidean algorithm, but I still don't see how to take ...
3
votes
1answer
49 views

On the proof of Lucas' theorem

Lucas theorem states that Let $m,n$ be two natural numbers, $p$ be a prime. Suppose that $m, n$ admit the following base $p$ representation $$m=m_0+m_1p+\cdots+m_sp^s,\qquad n=n_0+n_1p+\cdots+n_sp^...
10
votes
2answers
326 views

Prove that $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(5,2^n-3)=1$ where $n$ is a natural number. I didn't see an easy way to prove this using the Euclidean algorithm, but it seems true that both gcd'...
3
votes
3answers
78 views

Proving that a function is surjective

I want to prove that the function $\mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0$ defined as $(x,y) \mapsto 2^x \cdot (2y + 1) - 1$ is bijective. I have already proven that it is injective,...
1
vote
2answers
40 views

For a certain base $b$, the product $(12_b)(15_b)(16_b)$ is equal to $3146_b$. Let $s = 12_b + 15_b + 16_b$. What is $s$ in base $b$?

I have worked out the above problem in the following way: $(12_b)(15_b)(16_b)=(b+2)(b+5)(b+6)=3146_b=3b^3+b^2+4b+6$ $=>b^3+13b^2+52b+60=3b^3+b^2+4b+6$ $=>-2b^3+12b^2+48b+54=0$ $=>-b^3+6b^2+...
0
votes
1answer
32 views

Why This alternative way for retrieving the Original number from 2'S complement number works?

I was reading a book to learn about conversion from 2'S complement number to origianl binary number. During my past college study, I learened the following method for retrieving the Original number ...
3
votes
6answers
115 views

Proof that $n^2 - 5$ is not divisible by 8

The question is from one of the past exams in a course I am doing. I have gotten halfway through it but cannot figure out how to finish it off. So the first part was to prove that $4 \mid n^2 - 5 $ ...
4
votes
1answer
74 views

Understanding the proof for showing that there are infinitely many $n\in\mathbb{Z}^+$ such that $n!+1$ is divisible by at least two distinct primes

There is another post pertaining to this question; however, the other post does not address some specifics that concern me in the proof. Proof: Let $n=p-1, p \geq 7$. Then $p|(p-1)!+1$. We will show ...
1
vote
1answer
24 views

A question on divisibility of binomial coefficient

In this paper, page 3, theorem 4, the author claimed that If $m, n, k$ are three positive integer such that $\text{gcd}(n, k)=1$ then $\binom{mn}{k}\equiv 0\pmod n$. And he proved it as ...
3
votes
1answer
39 views

Integral solution and odd prime

Here is my question: Let $p\neq 7$ be an odd prime. Suppose that only one of the two equations, $$ x^2 + 7y^2 = p, \quad x^2 - 7y^2 = p $$ has integral solution $(x,y)$. Prove that $p \equiv 3\...
0
votes
2answers
119 views
-1
votes
1answer
28 views

Injectivity in functions [closed]

Sorry, I know that it has to be a very simple problem, but I'm frustrated because of it. Let $f, g : \mathbb{N}^3 \rightarrow \mathbb{N}$: $f(x,y,z) = 3^x \cdot 5^y \cdot 7^z$ and $g(x,y,z) = 3^x + ...
0
votes
1answer
25 views

Solving simple diophantine equation with modulos

I need to solve this diophantine equation using a positive integer $x$: $$x^2 + 42x + 21 \equiv 0 \mod 105$$ I think it will be easier if I could use the prime factors of $105$ to get a system of ...
1
vote
3answers
32 views

Diophantine equations using Euclidean algorithm

I solved two systems of Diophantine equations using the Euclidean algorithm and I can't figure out where I went wrong because the solutions I test aren't working but I have rechecked my work several ...
5
votes
1answer
62 views

Is there a formula for $(\frac{3}{p})$?

In number theory we learn when $2$ is a quadratic residue: $ \left( \frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}}$ It takes a moment to verify that $\displaystyle \frac{p^2 - 1}{8} \in \mathbb{Z}$ ...
1
vote
1answer
33 views

construct a unit on $\mathbb{Z}[\sqrt[3]{7}]$?

how might I construct a unit on $\mathbb{Z}[\sqrt[3]{7}]$? Can it be done using pigeonhole principle as with square roots and Pell equation. I had been reading about the Voronoi continued fraction or ...
1
vote
2answers
46 views

Equation involving the Jacobi symbol: $\left( \frac {-6} p \right) = 1$?

I have to determine the values of $p \in \{0, \dots, 23 \}$ such that $\left( \frac {-6} p \right) = 1$. I have that: $$\left( \frac {-6} p \right) = \left( \frac 2 p \right) \left( \frac {-3} p \...
-1
votes
1answer
55 views

Given $N$ find the number of natural numbers less than $N$ that may be written in the form $\frac{(k)(k+1)}{2}$

Given $N$, find the number of natural numbers less than $N$ that may be written in the form $$\frac{k(k+1)}{2},$$ where $k\in \Bbb N$. I know that the answer to this problem is approximately $\sqrt {...
-1
votes
0answers
28 views

Confusion between Sequences and Number theoretic functions.

I've just started learning Number Theoretic function,the definition of ,Number Theoretic function,which i've just read created some confusion b/w Number Theoretic function & Sequences. The ...
6
votes
2answers
212 views

Find the $k$ such that $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$.

Find all positive integers $k$ such that for any positive integer $n$, $2^{(k-1)n+1}$ does not divide $\frac{(kn)!}{n!}$. From olympiad problem I'm curious So far no one to solve this problem,Maybe ...
1
vote
1answer
43 views

Is the difference between $ 2$ coprimes always either 1 or prime number?

If a and b are both positive and coprime with $a > b$, Is $a - b$ always either $1$ or prime number? Can $a - b$ be composite number?
0
votes
2answers
36 views

How to explain the rationality of a solution?

This an exercise from an elementary number theory textbook: "The curve $$y^2 = x^3 + 8$$ contains the points $(1, -3)$ and $(-7/4, 13/8)$. The line through these two points intersects the curve in ...
1
vote
1answer
83 views

Even Digit Series (2,4,6,8,20,…) [duplicate]

I have a series of numbers whose Nth term is a number whose all of the digits are even. The series is of course divergent , but i am interested in finding a formula to find the Nth term of this series....
4
votes
4answers
80 views

Showing that there are infinitely many integer solutions for the hyperbolic formula $|a^2 - 26 b^2| = 1$

I want to show that the formula $$ | a^2 - 26\cdot b^2| = 1$$ has infinitely many solutions $(a, b) \in \mathbb{Z}^2$. First I tried to solve the formula for one of the two variables, to get ...
2
votes
2answers
30 views

Use of greatest common divisor to calculate unknown

We have three numbers $x ,y, z$. If we know the values of $x$ and $z$ then is it correct to say that $y$ should be a multiple of $z/\gcd(z,x)$ for the expression shown below to be true? Here $\gcd$ ...
4
votes
0answers
67 views

Skiponacci: $p | a_p$ Alternate Solution

For the Skiponacci sequence: $a_0=3, a_1=0, a_2=2,$ and $a_{n+1}=a_{n-1}-a_{n-2}$ for $n>2$, prove that any prime $p$ divides $a_p$. Is there any alternate solution other than using ...
0
votes
1answer
42 views

Basic question with coprimes and modulos

I started reading about Modular Arithmetic and solving some random basic exercises, and this one appeared: "Find an integer number $a$ such that any $b$ coprime with 34 is congruent to $a^k \mod34$ ...
3
votes
2answers
59 views

Origin of Almost Perfect Numbers

Let $N$ be a positive integer. $N$ is called a perfect number if the sum of its positive divisors denoted by $\sigma(N)=2N$. For example $6$ is a perfect number since: $\sigma(N)=1+2+3+6=12=2(6)$. ...
0
votes
1answer
31 views

System of linear congruence when not relatively prime

I am new to Abstract Algebra and understand how to solve when the mods are relatively prime, but I am struggling when they aren't relatively prime. I have a system of of linear congruences that I ...
2
votes
2answers
71 views

If $d=\gcd\,(f(0),f(1),f(2),\cdots,f(n))$ then $d|f(x)$ for all $x \in \mathbb{Z}$

$\textbf{Question.}$ Let $f$ be a polynomial of degree $n$ which takes only integral values. If $d=\gcd\,\{f(0),f(1),f(2),\cdots,f(n)\}$ then show that $d|f(x)$ for all $x \in \mathbb{Z}$. How ...
1
vote
0answers
24 views

Analogy to Four Squares Theorem.

Is there a multivariate and univariate polynomial analogy to Lagrange's sum of four squares?
1
vote
1answer
36 views

Cyclic prime groups

can I have a refrence to an introduction (not super beginner level, one after) of the multiplicative group $Z/ZP$? I know that it is cyclic. I am interested in known properties of the generators. ...
1
vote
1answer
43 views

Succession in Peano axioms

In "Analysis I" - Herbert Amann states: "The natural numbers consist of a set $ N$ , a distinguished element $0\in N$ and a function $v:N\to N^*$ with the following properties: ($N0$) $v$ is ...
1
vote
2answers
34 views

Finding unknown numbers using $ LCM $ and $ HCF $

Find two numbers, $A$ and $B$, both smaller than $100$, that have a lowest common multiple of $450$ and a highest common factor of $15$. I know that this involves the formula of $A × B = LCM × HCF$ ...
0
votes
1answer
46 views

What am I missing in this induction proof?

Prove that if $g:\mathbb{N}\rightarrow \mathbb{N}$ and $\forall x,y\in \mathbb{N}, x<y\Rightarrow g(x)<g(y)$ then $n\leq g(n)\space\space\space \forall n\in \mathbb{N}$ My proof so far (...
6
votes
1answer
24 views

In general what happens in Conway's Prime Game given $2^n$, with $n$ composite, as the initial value?

The fractions are $$\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \...
1
vote
1answer
46 views

Prove $(ah,bk)=(a,b)(h,k)\left(\frac{a}{(a,b)},\frac{k}{(h,k)}\right)\left(\frac{b}{(a,b)},\frac{h}{(h,k)}\right)$

I had an idea and was wondering if it works. I seem to have gotten away quite cheaply. The many multiplications on the right side made me consider the prime divisors: $p\mid (ah,bk)\Rightarrow p\mid ...
0
votes
1answer
57 views

What are the number of solutions of $x+y+z=r$ .By just giving the solutions as even/odd pairs?

In Detail:- I want to know that if I just consider odd/even then $x+y+z =r$ which having solutions $= (n+r-1)C(r-1)$ . But when we classify the numbers as just odd and even then there will be reduced ...
1
vote
2answers
50 views

How to prove that set of prime number such $p\equiv 7 [12]$ is infinite?

We have $n \ne 3k$ with $k\in \mathbb{N}$ and the integer $4n^2+3$. I think the first thing is to prove that this integer has a prime factor $p\equiv 7 [12]$. I don't have idea to begin. Thanks in ...
0
votes
0answers
31 views

A more elegant proof of $[(a,b),c]=([a,c],[b,c])$.

So assuming the fundamental theorem of arithmetic and using the definitions $(a,b)=\prod_i^{\infty}p_i^{\min\left\{a_i,b_i\right\}}$ and $[a,b]=\prod_i^{\infty}p_i^{\max\left\{a_i,b_i\right\}}$ with $...
4
votes
0answers
123 views

Diophantine equation with binomial coefficient

Suppose that $p$ is a prime number and $p \le q \le p^2$ is an integer. How many solutions are there to the following equation? $$\binom{p^2}{q}-\binom{q}{p}=1$$ This question was proposed ...
4
votes
5answers
171 views

Find $3^{333} + 7^{777}\pmod{ 50}$

As title say, I need to find remainder of these to numbers. I know that here is plenty of similar questions, but non of these gives me right explanation. I always get stuck at some point (mostly right ...
6
votes
0answers
74 views

Integer divisibility

Given a (not strictly) decreasing sequence of natural positive numbers $a_1, a_2, \dots, a_n$ prove that $$ \prod_{i<j} j-i \quad\big|\quad \prod_{i<j} a_i - a_j - i +j $$ I already know a ...
-1
votes
3answers
888 views

Find the first digit of a huge product in case of multiplication

Let there be many numbers $a_1,a_2,a_3,\dots,a_n$. I want to find the first digit of their product, i.e. of $A=a_1\times a_2\times a_3\times a_4\times \dots\times a_n$. These numbers are huge and ...
1
vote
1answer
36 views

Compute $(a_n,a_{n+1}) \forall n$ with $a_n$ the fibonacci sequence

Here my attempt: Employ the euclidean algorithm, i.e. $\forall r_0,r_1 \exists q,b: r_0 = q\cdot r_1+r_2, 0\le r_2 \lt r_1$. $q,b$ are determined uniquely. Since the definition of the fibonacci ...