what is Fp(n) and what is a "carry" and I don't understand "adding m and n-m in base p" ? Don't mind the highlights, thank you

[miregal]

 

[Dr.Peterson]

what is Fp(n) and what is a "carry" and I don't understand "adding m and n-m in base p" ? Don't mind the highlights, thank you
View attachment 23924

I'll demonstrate with an example, and see whether the theorem works.

Take the prime 3, and the binomial coefficient [MATH]{{12}\choose{5}}=792[/MATH]. So p = 3, n = 12, m = 5, n - m = 7.

In base 3, m = 12 and n-m = 21. Add them in base 3:

1 1
  1 2
  2 1
-----
1 1 0 = 12 = n

There are two carries, the 1's in the top line, one that arose from adding 2+1 to get 10 in the right column, and one that arose from adding 1+1+2 to get 11 in the second column.

And 792 = 2^3*3^2*11 is divisible by 3^2. So it worked.

Searching for this theorem, I found, among others, the following:


Though this sounds different, it is equivalent to the version you are asking about. The dividend in this example is too large to check, but the addition does involve 3 carries.

Wikipedia states the theorem and gives an example using base 2. It also has a link explaining the word "carries".

I almost missed the first part of your question, as you put the question in the title. I can't answer it without seeing the context, which presumably defined [MATH]F_p(n)[/MATH].

POSTSCRIPT:
I searched for your source and found it here. As expected, it defined the symbol you asked about!

 

[miregal]

Thanks for the reply but I don't understand this part, could you tell me which topic should I check out to understand this expression:



and also, I know what Fp(n) denotes but what symbol is it?

 

[Dr.Peterson]

Thanks for the reply but I don't understand this part, could you tell me which topic should I check out to understand this expression:

View attachment 23960

and also, I know what Fp(n) denotes but what symbol is it?

If you have never learned how to do addition in other bases, you will have to do so in order to understand this. I take it the link in Wikipedia didn't help? I see I failed to include a link as I intended to, though it's easy enough to find: https://en.wikipedia.org/wiki/Kummer's_theorem links to https://en.wikipedia.org/wiki/Carry_(arithmetic). For more detailed instruction, here is one source: https://online.math.uh.edu/Math2303-unpaid/ch1/s15/2303-Section-15.pdf (Admittedly, this way of writing an addition is not taught universally, so it is understandable that you may not recognize it.)

I don't know what you are asking about [MATH]F_p(n)[/MATH], which is a notation invented for the statement of this theorem. The symbol is what you typed! The meaning is what they stated, which you say you know. (Any non-standard notation will be defined before being used in any paper.) So what is it that you don't understand?

They've defined [MATH]F_p(n)[/MATH] as "the number of entries in the first n rows of Pascal's triangle not divisible by p". Pascal's triangle begins

1
1 1
1 2 1
1 3 3 1

and so on. So, for example, [MATH]F_3(4)[/MATH] is the number of those 10 entries I just wrote that are not divisible by 3; since only two are divisible by 3, [MATH]F_3(4) = 8[/MATH].

 

[JeffM]

Thanks for the reply but I don't understand this part, could you tell me which topic should I check out to understand this expression:

View attachment 23960

and also, I know what Fp(n) denotes but what symbol is it?

First, I am pretty sure that your nickname contains a grammatical error: ”stabat” is singular and “patriae” is plural.

As for F_p(n), it is just a specialized use of function notation. If you are used to function notation at all, this could just as easily have been written F(p, n). If you are familiar with logarithms, we could write them as

[MATH]log(b, x)[/MATH] instead of [MATH]log_b(x).[/MATH]
It is a way of saying that a function is one function out of a “family” of related functions.

Your other question is about the bases of systems of numeration. You are fully familiar with decimal numerals as a way to identify numbers.

[MATH]245 \equiv (2 * 10^2) + (4 * 10^1) + (5 * 10^0)[/MATH]
The number is broken down into a sum of products with factors smaller than 10 and powers of 10. For each of the ten non-negative integers smaller than 10, a unique symbol is used, and those 10 symbols are called the decimal digits.

It should be obvious that there is nothing magical about the number 10. We can construct a system using any number. As a practical matter, the technicalities of digital computers are best worked with using systems of numeration based on two (binary numerals) and on sixteen (hexadecimal numerals). Systems of numeration not based on two, ten, or sixteen currently have few (if any) uses of BROAD practical importance although a system may be very useful in some specialized application.

So you already know how the decimal numeral system works. How would a system based on the number three work. We need three symbols to represent the three non-negative integers less than three. Let’s use 0, 1, and 2.

Now consider the number five. We can express it in decimal notation as

[MATH]3 + 2 = 3^1 + 2 * 1 = 1 * 3^1 + 2 * 3^0.[/MATH]
So the number five in ternary notation (notation based on three symbols) is 12 just as Dr. Peterson said.

How about the number twelve?

[MATH]12 = 9 + 3 + 0 = 1 * 3^2 + 1 * 3^1 + 0 * 3^0.[/MATH]
So the number twelve in ternary notation is 110.

Now we need a new addition table.

0 + 0 = 0
0 + 1 = 1
0 + 2 = 2
1 + 1 = 2
1 + 2 = 10
2 + 2 = 11

and a new multiplication table

0 * 0 = 0
0 * 1 = 0
0 * 2 = 0
1 * 1 = 1
1 * 2 = 2
2 * 2 = 11.

We are set to go.

Twelve minus five is

[MATH]110 - 12 = 100 + 10 + 0 - 10 - 2 = (10)(10) + 10 - 10 - 2 = (2 + 1)(10) + (2 + 1)(1) - 10 - 2 =\\ 20 + 10 + 2 + 1 -10 - 2 = 20 + 1 = 21.[/MATH]What is the decimal representation of the number expressed in ternary representation as 2? Does it look as though this is correct?

Now use the multiplication table to find the product as Dr. Peterson did.

Try expressing the number two hundred and forty-five in ternary notation.

Lots of information about binary and hexadecimal numerals on the web.

 

[miregal]

If you have never learned how to do addition in other bases, you will have to do so in order to understand this. I take it the link in Wikipedia didn't help? I see I failed to include a link as I intended to, though it's easy enough to find: https://en.wikipedia.org/wiki/Kummer's_theorem links to https://en.wikipedia.org/wiki/Carry_(arithmetic). For more detailed instruction, here is one source: https://online.math.uh.edu/Math2303-unpaid/ch1/s15/2303-Section-15.pdf (Admittedly, this way of writing an addition is not taught universally, so it is understandable that you may not recognize it.)

I don't know what you are asking about [MATH]F_p(n)[/MATH], which is a notation invented for the statement of this theorem. The symbol is what you typed! The meaning is what they stated, which you say you know. (Any non-standard notation will be defined before being used in any paper.) So what is it that you don't understand?

They've defined [MATH]F_p(n)[/MATH] as "the number of entries in the first n rows of Pascal's triangle not divisible by p". Pascal's triangle begins

1
1 1
1 2 1
1 3 3 1

and so on. So, for example, [MATH]F_3(4)[/MATH] is the number of those 10 entries I just wrote that are not divisible by 3; since only two are divisible by 3, [MATH]F_3(4) = 8[/MATH].

Thank you so much

 

[miregal]

First, I am pretty sure that your nickname contains a grammatical error: ”stabat” is singular and “patriae” is plural.

As for F_p(n), it is just a specialized use of function notation. If you are used to function notation at all, this could just as easily have been written F(p, n). If you are familiar with logarithms, we could write them as

[MATH]log(b, x)[/MATH] instead of [MATH]log_b(x).[/MATH]
It is a way of saying that a function is one function out of a “family” of related functions.

Your other question is about the bases of systems of numeration. You are fully familiar with decimal numerals as a way to identify numbers.

[MATH]245 \equiv (2 * 10^2) + (4 * 10^1) + (5 * 10^0)[/MATH]
The number is broken down into a sum of products with factors smaller than 10 and powers of 10. For each of the ten non-negative integers smaller than 10, a unique symbol is used, and those 10 symbols are called the decimal digits.

It should be obvious that there is nothing magical about the number 10. We can construct a system using any number. As a practical matter, the technicalities of digital computers are best worked with using systems of numeration based on two (binary numerals) and on sixteen (hexadecimal numerals). Systems of numeration not based on two, ten, or sixteen currently have few (if any) uses of BROAD practical importance although a system may be very useful in some specialized application.

So you already know how the decimal numeral system works. How would a system based on the number three work. We need three symbols to represent the three non-negative integers less than three. Let’s use 0, 1, and 2.

Now consider the number five. We can express it in decimal notation as

[MATH]3 + 2 = 3^1 + 2 * 1 = 1 * 3^1 + 2 * 3^0.[/MATH]
So the number five in ternary notation (notation based on three symbols) is 12 just as Dr. Peterson said.

How about the number twelve?

[MATH]12 = 9 + 3 + 0 = 1 * 3^2 + 1 * 3^1 + 0 * 3^0.[/MATH]
So the number twelve in ternary notation is 110.

Now we need a new addition table.

0 + 0 = 0
0 + 1 = 1
0 + 2 = 2
1 + 1 = 2
1 + 2 = 10
2 + 2 = 11

and a new multiplication table

0 * 0 = 0
0 * 1 = 0
0 * 2 = 0
1 * 1 = 1
1 * 2 = 2
2 * 2 = 11.

We are set to go.

Twelve minus five is

[MATH]110 - 12 = 100 + 10 + 0 - 10 - 2 = (10)(10) + 10 - 10 - 2 = (2 + 1)(10) + (2 + 1)(1) - 10 - 2 =\\ 20 + 10 + 2 + 1 -10 - 2 = 20 + 1 = 21.[/MATH]What is the decimal representation of the number expressed in ternary representation as 2? Does it look as though this is correct?

Now use the multiplication table to find the product as Dr. Peterson did.

Try expressing the number two hundred and forty-five in ternary notation.

Lots of information about binary and hexadecimal numerals on the web.

Thank you so very much, and I know adjective must agree with the noun in Latin but these are 2 random words I found on a page, so I don't really care and know what they mean